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?
1
-
$\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 RicherbyApr 18, 2017 at 8:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
