Radix Sort and Counting Sort: Worked Examples, Complexity and Exam Traps
See how counting sort builds cumulative positions and how LSD radix sort depends on stable digit passes. Two traced examples turn formulas and exam traps into checks you can reproduce.
KnowledgeGate Team
Exam prep & CS education

Both algorithms avoid element-to-element comparisons, and counting sort can even work inside radix sort. Yet their inputs, passes and complexity parameters are different. Counting sort uses frequency counts and cumulative positions, while LSD radix sort requires stable digit-level sorting on every pass.
Counting sort assumes a finite integer-key range. Negative keys work after an offset such as x-min, and records work when the complete record moves with its extracted integer key. Direct indexing is a poor fit for decimals without a finite scaling rule or for an unbounded key range.
Radix sort and counting sort are non-comparison sorts with different jobs
Counting sort records each complete key's frequency, converts frequencies to cumulative positions, then writes the output. LSD radix sort processes digits from least significant to most significant, using a stable digit-level sort on every pass. Neither contradicts the comparison-sorting lower bound because neither relies only on key comparisons.
Algorithm | Unit processed | Required bound | Stable requirement | Typical use |
|---|---|---|---|---|
Counting sort | Complete key | Compact key range | Needed for records and radix passes | Small, dense integer range |
LSD radix sort | One digit per pass | Fixed base and bounded digit length | Mandatory between passes | Bounded-length integer keys |
Use GATE CS Exam Preparation as the wider subject route.
Counting sort worked example: frequencies, prefixes and stable placement
Take A = [4_a,2_b,2_c,8_d,3_e,3_f,1_g,0_h]. Its keys span 0 to 8, so allocate C[0..8]. Frequency counting gives C = [1,1,2,2,1,0,0,0,1]; prefix sums give C = [1,2,4,6,7,7,7,7,8]. Now C[x] counts input keys less than or equal to x.
Scan right to left and place each record at B[C[key]-1], then decrement C[key]:
0_h -> B[0], 1_g -> B[1], 3_f -> B[5], 3_e -> B[4], 8_d -> B[7], 2_c -> B[3], 2_b -> B[2], 4_a -> B[6].
Thus B = [0_h,1_g,2_b,2_c,3_e,3_f,4_a,8_d]. The order 2_b before 2_c and 3_e before 3_f demonstrates stability.
The cumulative-count invariant explains both the position and the decrement. Before placement, C[x]-1 is the last output index available to key x. After placing one record, decrementing C[x] exposes the preceding slot for the next equal key. Scanning from right to left means the later equal record occupies the later slot, so earlier equal records remain earlier in B. With negative keys, access C[key-min] but leave the stability argument unchanged.

LSD radix sort worked example: three stable base-10 passes
For A = [170,45,75,90,802,24,2,66], use base b=10 and treat shorter numbers as having leading zeroes. The maximum, 802, has three digits, so exactly three stable passes are needed:
Ones:
[170,90,802,2,24,45,75,66]Tens:
[802,2,24,45,66,170,75,90]Hundreds:
[2,24,45,66,75,90,170,802]
The tens buckets are 0:[802,2], 2:[24], 4:[45], 6:[66], 7:[170,75], 9:[90]. After pass p, the array is sorted by its last p digits. The three passes therefore establish one-digit, two-digit and full-key order.
The radix invariant follows by induction. After the ones pass, records are ordered by the last digit. Assume they are ordered by the last p digits. A stable pass on digit p+1 groups records by that digit without changing the order inside each group, so the last p+1 digits are ordered. An unstable pass breaks the induction because equal current digits may reverse the lower-digit order already established.
![LSD radix sort on [170,45,75,90,802,24,2,66] in base 10, with the ones, tens and hundreds pass outputs and the tens-pass buckets.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784215359750_aaxfbu.jpg)
Counting sort versus radix sort: range, digits and base
Let n be the record count, k=max-min+1 the counting-sort range, d the processed digit count, and b the radix. Stable counting sort takes Theta(n+k) time and Theta(n+k) auxiliary space. LSD radix sort with reused counting-sort arrays takes Theta(d(n+b)) time and Theta(n+b) space.
Our counting example has n=8, k=9, so its cost expression is 8+9. For [0,7,42,999999,1000000], n=5 but k=1000001, making direct counting wasteful. Base-10 radix sort instead has d=7, b=10, giving 7(5+10). These are asymptotic expressions, not instruction counts.
For the eight-record radix example, base 10 gives the proxy 3(8+10)=54. Base 2 needs d=10 because 802 is 1100100010 in binary, giving 10(8+2)=100. A single base-1000 digit gives 1(8+1000)=1008. These values do not predict exact running time, but they show why neither the smallest nor the largest base is automatically best: d falls as b grows, while the count array grows with b.
Choose counting sort for a small dense range, radix sort for bounded-length keys with a small digit alphabet, and comparison sorting when either auxiliary structure is unreasonable. Sorting Algorithms: Complexity and Comparison compares the full sorting family and proves the comparison lower bound. Counting-sort placement and stable radix passes need separate full traces because their k, d and stability conditions do not appear in a comparison-sort decision tree.
Stability is optional for counting sort but mandatory for LSD radix sort
Right-to-left placement preserves equal-key input order. Repeating each key from a frequency table still sorts plain integers, but loses attached-record order, so not every counting-sort implementation is stable.
For A=[21_a,11_b,12_c], a stable ones pass gives [21_a,11_b,12_c]. In the tens pass, digit-1 records must remain [11_b,12_c], producing [11_b,12_c,21_a]. Reversing them gives [12_c,11_b,21_a], which is numerically wrong. Any unstable LSD pass can destroy order already established by less significant digits.
Radix sort and counting sort exam traps: six fixed checks
[-2,3]needsk=3-(-2)+1=6slots; map keyxto indexx+2.Maximum key 802 needs three base-10 passes.
Raw counts are frequencies; cumulative counts identify positions.
Right-to-left output scanning preserves equal-key order.
LSD radix sort fails when its per-digit sort is unstable.
Theta(n+k)becomesTheta(n)only whenk=O(n).
A larger b may reduce d, but it also enlarges the buckets processed per pass. Compare the whole d(n+b) expression, not radix alone. More than 10 Radix & Counting Sort practice questions reinforce these checks. Use the GATE Test Series for mixed timed practice.
Radix sort and counting sort: the short version and next step
Counting sort handles whole keys.
Radix sort handles one digit at a time.
Counting sort costs
Theta(n+k).Radix sort costs
Theta(d(n+b)).Stability is essential between LSD passes.
Counting sort produces [0,1,2,2,3,3,4,8], while LSD radix sort produces [2,24,45,66,75,90,170,802]. GATE Guidance by Sanchit Sir places sorting inside a structured subject sequence. Greedy Algorithms: Strategy and Problems is the next algorithm-design lesson.
Self-test: Sort [329,457,657,839,436,720,355] with base-10 LSD radix sort and record every pass.
Check: ones [720,355,436,457,657,329,839]; tens [720,329,436,839,355,457,657]; hundreds [329,355,436,457,657,720,839].
Keep learning
Radix and Counting Sort MCQs: 12 Solved Questions with Explanations
Solve 12 Radix and Counting Sort MCQs with compact explanations, two hand traces, a counting-sort example and the complexity patterns exams repeatedly test.
Selection Sort Explained: Step-by-Step Trace, Complexity and Exam Traps
Learn the invariant behind Selection Sort, trace every pass, derive its exact comparison count, and avoid common stability and swap-count traps.
Merge Sort Interview Questions and Answers: Traces, Complexity, and Code
Prepare crisp merge sort interview answers through a fully traced array, boundary-safe Java implementation, complexity proof, stability example, and inversion-count follow-up.
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps
Learn what makes Prim's greedy choice safe, trace every key update on a six-vertex graph, and avoid the mistakes that derail MST questions.





