Counting Sort and Radix Sort

Counting and radix sorting exploit bounded integer keys rather than comparing arbitrary pairs. Counting sort stores how many times each key occurs; stable placement turns counts into output positions. Least-significant-digit radix sort repeatedly performs stable counting passes on digits. These can beat comparison sorting when the key representation and memory range are suitable, but they do not sort arbitrary strings, negative integers or unbounded values without additional design.

Prerequisites: Frequency arrays; stable sorting; loops.

Build the idea

1. 1. Count a bounded value range

   For keys in 0..K, allocate K+1 counters initialized to zero. frequency[v] is the number of copies of v. Reading each value increments one counter. If K is a billion, even a handful of input values would require an impractical counting array. The relevant bound is the value RANGE, not just the number of input elements.

2. 2. Convert frequencies to ending positions

   Replace count[v] by the cumulative number of keys ≤v. For [2,0,2,1], frequencies [1,1,2] become cumulative [1,2,4]. Process the original input right to left and place each key at --count[key]. Later equal-key records get later slots, preserving their input order. The integer-only output cannot display record stability directly, but the same placement of associated records is stable.

3. 3. Build decimal radix passes

   Radix handles 0..10^9 here using an unsigned long-long storage type and base 10. At place 1 sort stably by the ones digit; at 10 by tens; then hundreds and so on until the largest value has no remaining digit. Treat missing leading digits as zero. The second complete program is separate from the first, so its input does not require K.

4. 4. Explain why stability matters across digits

   After the first pass on [21,13,12], order by ones is [21,12,13]. A stable tens pass gives [12,13,21], retaining ones order among values sharing the same tens digit. An unstable tens pass could reverse 12 and 13 and break the already established lower-digit order. Inductively, after d passes the array is sorted by its lowest d digits.

5. 5. State representation and safety limits

   This radix program accepts NONNEGATIVE integers only, up to 10^9. It does not interpret signed negatives by their unsigned bit patterns. Its place variable is wide enough to multiply by ten past the largest supported decimal position without overflow. Extending to the entire unsigned range would need an explicit overflow guard or fixed-pass design. All-zero input needs no pass and is already sorted.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n,K;
    std::cin>>n>>K;
    std::vector<int>a(n),count(K+1,0),out(n);
    for(int&x:a){
        std::cin>>x;
        ++count[x];
    }
    for(int value=1;value<=K;++value){
        count[value]+=count[value-1];
    }
    for(int i=n-1;i>=0;--i){
        out[--count[a[i]]]=a[i]; // Stable right-to-left placement.
    }
    for(int i=0;i<n;++i){
        std::cout<<out[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

Counting sort: O(n+K+1) time and O(n+K+1) auxiliary memory for counts and stable output. Radix with base B and D processed digits: O(D(n+B)) time, O(n+B) extra memory. Here B=10 and D≤10 for values≤10^9. These representation-dependent bounds do not contradict the Ω(n log n) general comparison lower bound.

Example input and output

Counting program: read n K, n in 0..200000, K in 0..1000000, then n integers in 0..K. Print ascending values.

Input

4 2
2 0 2 1

Output

0 1 2 2

Counts [1,1,2] and cumulative ends [1,2,4] place the two 2s into the final two positions.

Read n (0..200000), then n nonnegative integers at most 10^9. Print ascending order.

#include<iostream>
#include<vector>
#include<algorithm>
void radixSort(std::vector<unsigned long long>&a){
    unsigned long long largest=0;
    for(auto x:a){
        largest=std::max(largest,x);
    }
    std::vector<unsigned long long>out(a.size());
    for(unsigned long long place=1;largest/place>0;place*=10){
        int count[10]={};
        for(auto x:a){
            ++count[(x/place)%10];
        }
        for(int d=1;d<10;++d){
            count[d]+=count[d-1];
        }
        for(int i=(int)a.size()-1;i>=0;--i){
            int digit=(a[i]/place)%10;
            out[--count[digit]]=a[i]; // Each digit pass must be stable.
        }
        a.swap(out);
    }
}
int main(){
    int n;
    std::cin>>n;
    std::vector<unsigned long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    radixSort(a);
    for(int i=0;i<n;++i){
        std::cout<<a[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Input

3
21 13 12

Output

12 13 21

Ones order is [21,12,13]; stable tens order becomes [12,13,21].

Complexity: O(D(n+10)) time, O(n+10) additional space, D≤10 under the stated bound.

Practical applications

Choose counting sort for a small dense key range, radix for bounded nonnegative integer representations with many elements, and std::sort for general keys or unknown/sparse large ranges. Coordinate compression can make frequencies compact but itself usually needs sorting, so it is not a free linear-time sorting replacement.

Check your understanding

Why must each LSD radix digit pass be stable?

Put it into practice

Test the radix program on [100,0,10,1,100] and all-zero input.