Radix Sort

LSD · stable per-digit passes

1:00

Sort integers in linear time by processing one digit at a time with stable counting-sort passes, never comparing two keys directly.

By the end, you can

Explain why radix sort is called a non-comparison sort and how that lets it escape the Ω(n log n) lower bound.
Trace all digit passes of LSD radix sort on a concrete array, computing the correct bucket placement for each pass.
State why each per-digit pass must be a stable sort and demonstrate with an example what goes wrong when stability is violated.
Distinguish LSD from MSD radix sort in terms of traversal direction, recursion structure, stability, and use cases.
Derive the Θ(d·(n+k)) time complexity and explain when it simplifies to Θ(n).
State the O(n+k) auxiliary space requirement and explain why radix sort is not in place.
Decide whether radix sort or a comparison sort is the better tool for a given sorting problem.

Up next in Searching & Sorting