I'm reading the CLRS book and have a question about the following quote from the book.
In order for radix sort to work correctly, the digit sorts must be stable.
Why is stability required? Wouldn't Radix sort still produce correctly sorted output even if there was no consistency in ordering of identical values, since Radix sort sorts on every digit position?
Integers that are equal in some digit aren't always equal (e.g., 12 and 13).
Let's sort [13, 12] using a LSD-first radix sort (base 10). But we'll use an unstable sort for each digit.
First we sort by the 1's place, so the array becomes [12, 13].
Now we sort by the 10's places, but 12 and 13 have the same digit. Since the sort is unstable, the resulting array could be [12, 13] or [13, 12]. We don't know.
If the sort were stable we would be guaranteed to get a correctly sorted array.
