# Why does radix sort work?

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?

• 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. – David Richerby Apr 18 '17 at 8:46

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.