1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can probably figure out the answer by simulating radix sort with a pencil and paper and trying to see where an unstable sort could mess things up. If you succeed with that, I encourage you to post it as an answer. $\endgroup$ – David Richerby Nov 17 '18 at 14:16
2
$\begingroup$

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.

$\endgroup$

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.