Motivation

Radix Sort never compares two numbers directly. It groups them by one digit at a time using a stable helper sort, which lets it break the O(n log n) barrier that comparison sorts cannot.

Why learn Radix Sort?

• Linear-ish time: it runs in O(d * (n + k)) where d is the number of digits and k is the base (10 here). For numbers with a bounded number of digits, that is effectively O(n).
• Stable: equal values keep their relative order, which is exactly what makes the digit-by-digit passes combine correctly.
• A different idea: it shows that sorting does not have to mean comparing, an important insight for large integer or fixed-width keys.

The trade-off: it needs keys you can break into digits (here, non-negative integers) and some extra memory for the buckets.