1
$\begingroup$

I read the following in CRLS:

enter image description here

I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "piles of cards" is it referring to?

Perhaps I'm not able to follow the example with cards, and an example with actual numbers would be best.


In case it helps, sorting naively by MSD doe not seem to work, even if all values are d-digit numbers:

Input   (1)   (2)   (3)
        *      *      *
 321    132   321   321
 522    321   426   522
 132    426   522   132
 426    522   132   426

where (i) is the result of sorting the previous column by the ith-highest digit.

$\endgroup$
1
$\begingroup$

It would work, the only problem is that it will generate a lot of extra piles for the intermediate results that are difficult to track.

if the sorting algorithm sorts the $d$-digit numbers starting from their most significative digit it would create 10 piles at first (one pile for the numbers starting with 0, another one for those starting with 1 and so on) and then sort each pile recursively as explained in the book.

The problem is that to sort the pile of numbers starting with 0 the algorithm needs to create ten more piles (one for the numbers starting with 00, the second for the numbers starting with 01 and so on, the last pile is for the numbers starting with 09).

Thus we have created 19 piles until now. To sort the pile of the numbers starting with 00 we need to create 10 more piles. If this process continues until the $d$ digit are sorted you can imagine that a huge number of piles are created (how many?).

This are the extra piles that the book was referring to.

If yoy use LSD radix sort you don't have to split the numbers in piles at all. You can nust sort the input pile by last digit, then the same pile by the penultimate digit and so on, after $d$ steps you will end up with the expected result.

The intuition is the following: let $d$ be $2$ and let $83$, $19$ and $17$ be the input. The first step on MSD radix sort will place $17$ and $19$ before $83$. Then if you sort the same whole pile by the second digit you will end up with $83$ before $17$ which is wrong. You need to split the pile because you have to "remember" the previous sorting made by the algorithm, which is more "important". Conversely, the first step of LSD radix sort will place $83$ before $17$, then $19$. If you take the whole pile and sort it by the first digit you get $17$, $19$, $83$ which is correct. You don't need to split the pile because the current step of the algorithm is more "important" of the previous ones and it is allowed to "mess up" the previous ordering in any way (for example by placing $83$ after $17$ and $19$). This would work as long as the sorting algorithm used for each digit is stable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks I think I almost get it. You said "The problem is that to sort the pile of numbers starting with 0 the algorithm needs to create ten more piles (one for the numbers starting with 00, the second for the numbers starting with 01 and so on, the last pile is for the numbers starting with 09)." But why doesn't that happen with the LSD version? (i.e. instead of creating piles for numbers starting with 00*, 01*, 02*... wouldn't you need to create them for numbers ending in *00, *10, *20, etc), i.e. why don't you end up with as many piles in the LSD version? What am I missing? $\endgroup$ – Josh Mar 26 at 3:45
  • $\begingroup$ LSD radix sort always use the same pile. I'll update my answers soon $\endgroup$ – melfnt Mar 26 at 7:02
  • $\begingroup$ +1 I reworded your last paragraph a bit to say: "... With LSD you don't need to split the pile because on any given iteration, the current digit under consideration is more "important" for sorting than previous digits (their ordering should preclude the ordering of previous digits) so the [current iteration] is allowed to override the previous ordering as needed" $\endgroup$ – Josh Mar 30 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.