Subj : Re: LSD radix sort
To   : comp.programming
From : googmeister
Date : Thu Jul 21 2005 11:38 am

Duck Dodgers wrote:
> Here is a question that's been bugging me for a long time. Every
> description of the LSD radix sort says that it works from the least
> significant digit to the most significant,

Yes, that's right.

> but every implementation
> says the opposite by looping from the most significant digit to the
> least. Like in Algorithms in C:
>
> for (w = bytesword-1; w >= 0; w--)
>
> This goes from the most significant byte to the least, so wouldn't that
> be an MSD radix sort and an LSD radix sort would look like this?

I think you have misunderstood the convention described
in Sedgewick 10.1. Think of the sequence of digits as a string,
indexed left to right. The 0th digit is the most significant here.

> And then the MSD
> radix sort--if it's not completely ignored--is really complicated, but
> there's no explanation as to why it has to be when the LSD code
> practically screams MSD.

Uhh, see Sedgewick 10.3. It's neither really complicated nor ignored.

> Can somebody clear this up for me?

The LSD algorithm may scream MSD, but if you listen carefully
you'll hear that the resulting algorithm (by examining the digits
from most significant digit to least) is no longer correct. To
guarantee correctness you need to keep track of the groups of
strings that are already known to agree in their first k digits -
this is where the added complexity arises.

.