# Thread: Can it be done???

1. ## Can it be done???

Can the Radix/Bucket Sort be done using a linked list????

If so, How would one go about it...I am pretty bad and would ususally use a vector or array, but the program I am writing requires the linked list to be used.

2. The answer is easily googled... but here I go anyhoo.

For a radix sort you take the least significant digit...
IE: for the number 405, the 5.

You make a group of linked lists for each least significant digit encountered.

Now, combine these linked lists... (tail = head).

Now sort by the next significant digit and continue...

For example, consider the following set of data:
ABC, XYZ, BWZ, AAC, RLT, JBX, RDT, RDT, KLT, AEO, TLJ

On the first pass you'd get several linked lists (denoted by parenthesis)

(ABC, AAC) (TLJ) (AEO) (RLT, RDT, KLT) (JBX) (XYZ, BWZ)

Now combine....

ABC, AAC, TLJ, AEO, RLT, RDT, KLT, JBX, XYZ, BWZ

Now sort again by the next most significant digit...
(AAC) (ABC, JBX) (RDT) (AEO) (TLJ, RLT, KLT) (BWZ) (XYZ)

Combine...
AAC, ABC, JBX, RDT, AEO, TLJ, RLT, KLT, BWZ, XYZ

One last pass...
(AAC, ABC, AEO) (BWZ) (JBX) (KLT) (RDT, RLT) (TLJ) (XYZ)

Done!
AAC, ABC, AEO, BWZ, JBX, KLT, RDT, RLT, TLJ, XYZ

From: