1
$\begingroup$

I understand how radix sort works and how to implement it, but I don't understand why it works.

Are there any underlying mathematical or logical principles that it relies on?

$\endgroup$
  • $\begingroup$ I don't understand your question. In mathematics, "how" and "why" are the same thing, so I don't understand what you mean when you say that you understand how it works but not why it works. $\endgroup$ – David Richerby Apr 18 '17 at 8:46
2
$\begingroup$

Radix sort sorts numbers by sorting on the least significant digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the most significant digit first.

The key point to radix sort is that the digit sorts used in each iteration of radix sort are stable: numbers (digit here) with the same value appear in the output array in the same order as they do in the input array. Given this, you can convince yourself of the correctness of radix sort by simply observing how a set of two-digit numbers are sorted. (Actually, we are using mathematical induction on the number of digits. However, a simple example with a set of two-digit numbers suffices here.)

In the first iteration, the numbers are sorted by their least significant digits. Now consider the second iteration which then sorts these numbers by the leftmost digits. Given two number $a = a_1 a_0$ and $b = b_1 b_0$, if $a_1 \neq b_1$, then after the second iteration, they are in the right order. If $a_1 = b_1$, then we know that the order between $a$ and $b$ should be consistent with $a_0$ and $b_0$. This is the case because the digit sort used by the second iteration is stable.

$\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.