Non-Comparison Sorting Algorithms

Counting sort, radix sort, and bucket sort beat the O(n log n) comparison-sort floor by never comparing elements at all — they exploit known structure in the keys (small integer range, fixed digit count, or uniform distribution) to compute each element's final position directly through arithmetic and bucketing.

Recognize the pattern

• Keys are integers (or map cleanly to integers) with a range k that is not much larger than n.
• Problem says "sort ages 0-120", "sort grades", "sort by digit", or values are floats uniformly spread in [0,1).
• You need stable sorting as a subroutine (e.g., before radix sort, or sorting records by one field while preserving order on another).
• Interviewer hints at "can you beat O(n log n)?" — that phrase is the tell for a non-comparison sort.

Brute force → optimal

Brute force: comparison sort (merge/quick/heap sort) treats keys as opaque and compares pairs, paying Θ(n log n) comparisons no matter what the data looks like — this is provably optimal for comparison-based sorts (decision-tree lower bound) but wasteful when keys are small integers.

Optimal (counting sort): instead of comparing, count how many elements are ≤ each value, then place each element directly at its computed index. Cost is proportional to n + k, not n log n. When k = O(n), this is linear — strictly better than the comparison floor because it uses information (bounded integer range) that a generic comparison sort ignores.

Complexity from first principles

Counting sort

Three linear passes: (1) tally counts — n operations over the input; (2) prefix-sum the count array — k operations; (3) place elements by reading input right-to-left and writing to output using the count array — n operations. Total operations = n + k, so Time = O(n + k). Space: one count array of size k+1 plus one output array of size n → Space = O(n + k).

Radix sort

Run a stable counting sort (base b, so k=b) once per digit position. If the largest key has d digits, total work = d × O(n + b). With b=10 and d = O(log_b(max value)), Time = O(d·(n+b)); for fixed-width keys (e.g. 32-bit ints, d≈constant) this is effectively O(n). Space = O(n + b) (reused per pass).

Bucket sort

Distribute n elements into m buckets (an O(n) scan); if input is uniformly distributed, each bucket gets ~n/m elements. Sorting each bucket with insertion sort costs O((n/m)²) expected per bucket; summed over m buckets, expected Time = O(n + n²/m), which is O(n) when m = Θ(n). Worst case (all elements in one bucket): O(n²). Space = O(n + m).

Traced example — Counting sort on [4,2,2,8,3,3,1]

Reference implementation (Java)

static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int x : arr) count[x]++;
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];
    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        for (int x : arr) count[(x / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

Pitfalls

• Forgetting stability in the placement loop (e.g., iterating left-to-right instead of right-to-left) silently breaks radix sort, which depends on each digit pass being stable to build on the previous pass's order.
• Counting sort on a huge range — if k ≫ n (e.g., sorting 100 numbers spread across 0..10^9), the count array dominates memory and time; counting sort degrades badly and a comparison sort wins.
• Radix sort on negative numbers — the naive digit extraction breaks; requires an offset/bias step or separate handling of sign.
• Bucket sort with skewed input — if the distribution isn't roughly uniform, one bucket absorbs most elements and you pay O(n²) via that bucket's insertion sort.

When to use / when NOT — vs comparison sorts

Trade-off in one line: comparison sorts trade a guaranteed log n factor for zero assumptions about the data; non-comparison sorts trade that generality for linear time when the key structure cooperates.

Takeaways

• Non-comparison sorts win by using arithmetic on keys instead of pairwise comparisons — this only works when keys are integers (or digit-decomposable) with bounded range.
• Counting sort's core trick is the prefix-summed count array: count[i] becomes "how many elements are ≤ i", which is exactly the final index.
• Radix sort is just counting sort applied once per digit — its stability requirement per pass is non-negotiable.
• Bucket sort's performance is a bet on distribution uniformity; it degrades to O(n²) when that bet fails.

Recall: Why must the inner counting-sort pass in radix sort be stable, and what breaks if it isn't?

Synthesized from CLRS (Counting Sort, Radix Sort, Bucket Sort chapters) and standard interview-prep sorting references.