Radix Sort never compares two elements against each other. Instead, it looks at individual digits — ones, tens, hundreds — and uses those digits as bucket indices. Process every digit position from least significant to most significant, and the array sorts itself.
This breaks the O(n log n) lower bound for comparison sorts, achieving O(n·k) where k is the number of digit positions. For integers in a reasonable range, this can be linear.
Radix Sort never asks 'is A greater than B?' It reads a digit and places the number in bucket[digit]. That's it. Zero element-to-element comparisons.
LSD — least significant first Process digits from right to left (ones → tens → hundreds). This works because each pass is stable — equal digits preserve the order established by the previous pass.
Digits 0–9 = 10 possible values = 10 buckets. Every element goes into exactly one bucket per pass. Collecting buckets 0–9 back into the array gives a partially sorted result.
n = number of elements, k = number of digit positions. For 32-bit integers, k ≤ 10. For most practical inputs, this is effectively linear.
TIPWatch what happens to numbers with the same digit — they stay in the same relative order within their bucket (stable sort). This is exactly why LSD works: the stability of each pass preserves the work done by previous passes.
COLOUR LEGEND
Distributing — placing into bucket Collecting — reading from bucket