Intuition The ONE core ideaA number like 802 sequence of digits 8 , 0 , 2 one digit column at a time (and never comparing two whole numbers), we can sort faster than the "compare two things" limit. This page builds — from nothing — every symbol you need to see why that trick even makes sense.
Before you can trust the radix-sort machine in the parent note , you must own every piece of notation it fires at you. We build them in order, each one on top of the last. Nothing is used before it is drawn.
Definition Digit and place valueA digit is one symbol from a fixed alphabet of size k 0 , 1 , … , 9 row of digits , where each column carries a weight : the rightmost column counts ones, the next counts k k 2
Look at the figure below. The number 802 addressable by position .
The value is rebuilt from its columns like this:
802 = col 2 8 × 1 0 2 + col 1 0 × 1 0 1 + col 0 2 × 1 0 0
Intuition Why the topic needs thisRadix sort's entire strategy is "sort by column 0, then column 1, ...". If a number were an indivisible blob you could only compare two blobs. Because it is a sequence of columns , we can process one column across all numbers at once. Every symbol below exists to name a piece of this picture.
k k 0..9 k = 10 k = 256
The picture below shows the tray rack for k = 10 0 9 count array in the parent's code.
Intuition Why the topic needsk structure : keys are sequences over an alphabet of size k k k Counting Sort , which needs exactly k
n n items in the array — the pile of cards, not their digits. In the parent's list [ 170 , 45 , 75 , 90 , 802 , 24 , 2 , 66 ] n = 8
Common mistake The two easiest symbols to swapWhy it's tempting: n k Why it's wrong: n numbers in the pile; k symbols a single digit can be. In [ 170 , 45 , … ] n = 8 k = 10 n vs k n k
d d widest key needs. In our example the biggest key is 802 3 d = 3 d
How do we compute d how many times must I multiply k That question is answered by a logarithm.
Definition Logarithm basek log k log k ( m ) "To what power must I raise k m It undoes raising k log 10 ( 1000 ) = 3 1 0 3 = 1000
The figure shows the staircase of powers of 10 802
Intuition Why the topic needsd d only factor multiplying the per-pass cost. Whether radix sort beats O ( n log n ) d d
The parent code plucks column i (x // exp) % k. Three symbols hide here; we build each.
exp = the place weight (k i exp is 1 , k , k 2 , … selects which column you are reading . To read column i // exp, then chop off everything above it with % k.
Worked digit extraction on 802 10
column 0 : ( 802 // 1 ) % 10 = 2 column 1 : ( 802 // 10 ) % 10 = 0 column 2 : ( 802 // 100 ) % 10 = 8
// exp then % k, in that order
// exp slides the column you want into the ones position (division shifts right). % k then keeps only that one column and discards the higher ones (modulo chops the top off). Reverse the order and you would strip digits before aligning them — you'd read the wrong column.
Extract column i ( x // k i ) % k
O ( f ( n )) growth shape , not exact counts. Saying one counting-sort pass is O ( n + k ) at most like n + k
We build this properly in Big-O Notation . Here you only need the reading: O ( d ( n + k )) d n + k n log n n d
Intuition Why the topic needs Big-OThe whole selling point is "escape Ω ( n log n ) Ω lower bound, "grows no slower than". Comparison sorts are stuck at Ω ( n log n ) Comparison Sort Lower Bound ); radix dodges it because it never compares whole keys. Without Big-O you cannot even state that claim.
A sort is stable if items that tie on the sort key come out in the same relative order they went in. If Alice's 45 45
Intuition Why stability is load-bearingRadix sorts column by column. When two numbers tie on the current column, their correct order was already decided by the earlier (lower) columns. Stability is the promise that the current pass won't scramble that earlier work. Break stability and the parent's induction proof collapses. This is the entire subject of Stability in Sorting , and it is why the per-digit engine is Counting Sort (naturally stable) and not, say, an in-place quicksort.
Stable means ::: ties keep their original relative order
LSD = L east S ignificant D igit first: start at column 0 d MSD = M ost S ignificant D igit first: start at the leftmost column, split into k
MSD's recursion-into-buckets is exactly the shape of a trie and cousins the divide-of-Bucket Sort ; LSD is the flat, always-d direction and structure .
Place value: a number is columns of digits
Radix k: k symbols, k trays
Extract digit: floor div and modulo
Counting Sort: one stable pass
Stability: ties keep order
Test yourself — say the answer aloud, then reveal.
What does the radix k The number of distinct symbols one digit can be, i.e. the number of trays/buckets.
What does n k n k
Give the formula for d d = ⌈ log k ( max key + 1 )⌉
What does log k ( m ) "To what power must I raise k m
How do you extract column i x ( x // k i ) % k k i k
Why // exp before % k Division aligns the wanted column into the ones place; modulo then keeps only that column.
What does O ( d ( n + k )) Do d n + k
What does "stable" guarantee Items tying on the current key keep their original relative order.
Why does radix sort need stability So a later column's pass does not scramble the ordering earlier columns already fixed.
LSD vs MSD in one word each LSD = rightmost-first flat loop; MSD = leftmost-first recurse-into-buckets.