Non-comparison sort (counting / radix)

How does Non-comparison sort (counting / radix) work?

Counting sort needs keys from a known, small range. Make one counter for each possible key.

Walk the input once and tally every key. Now you know how many of each exist.

Turn those tallies into starting positions. A running total says where each key's block begins.

Walk the input again and drop each item at its position. Nothing was ever compared.

Radix sort applies the same idea one digit at a time. It starts from the least significant digit.

Every digit pass has to be stable. An unstable pass undoes the passes before it.

Sources: Wikipedia: Counting sort, Wikipedia: Radix sort

1. counts = [1, 1, 2]Sorting [2, 0, 2, 1]. One zero, one one, two twos.
2. starts = [0, 1, 2]Running totals give each key its first slot.
3. [0, _, _, _]The 0 lands in slot 0. Its start moves on by one.
4. [0, 1, 2, _]The 1 takes slot 1, and the first 2 takes slot 2.
5. [0, 1, 2, 2]The second 2 takes slot 3. Not one comparison happened.

function countingSort(arr, maxVal) {
    const counts = new Array(maxVal + 1).fill(0);
    for (const x of arr) counts[x]++;
    const out = [];
    for (let v = 0; v <= maxVal; v++) {
        while (counts[v]-- > 0) out.push(v);
    }
    return out;
}

function countingSort(arr: number[], maxVal: number): number[] {
    const counts: number[] = new Array(maxVal + 1).fill(0);
    for (const x of arr) counts[x]++;
    const out: number[] = [];
    for (let v = 0; v <= maxVal; v++) {
        while (counts[v]-- > 0) out.push(v);
    }
    return out;
}

def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1
    out = []
    for v, c in enumerate(counts):
        out.extend([v] * c)
    return out

function countingSort(array $arr, int $maxVal): array {
    $counts = array_fill(0, $maxVal + 1, 0);
    foreach ($arr as $x) $counts[$x]++;
    $out = [];
    for ($v = 0; $v <= $maxVal; $v++) {
        for ($c = $counts[$v]; $c > 0; $c--) $out[] = $v;
    }
    return $out;
}

    public static int[] countingSort(int[] arr, int maxVal) {
        int[] counts = new int[maxVal + 1];
        for (int x : arr) counts[x]++;
        int[] out = new int[arr.length];
        int k = 0;
        for (int v = 0; v <= maxVal; v++) {
            while (counts[v]-- > 0) out[k++] = v;
        }
        return out;
    }

    public static int[] CountingSort(int[] arr, int maxVal) {
        var counts = new int[maxVal + 1];
        foreach (int x in arr) counts[x]++;
        var outArr = new int[arr.Length];
        int k = 0;
        for (int v = 0; v <= maxVal; v++) {
            while (counts[v]-- > 0) outArr[k++] = v;
        }
        return outArr;
    }

A worked example of Non-comparison sort (counting / radix)

The k most frequent values

Return the k values that appear most often in an array.

Sorting the counts costs n log n. The question never asked for a full order.

Count every value with a map. A count can never exceed the array length.

Use the count itself as an index into a list of buckets. Read the buckets from the back.

function topKFrequent(nums, k) {
    const count = new Map();
    for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);

    // bucket i holds every value that appeared exactly i times
    const buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (const [value, c] of count) buckets[c].push(value);

    const answer = [];
    for (let c = buckets.length - 1; c >= 1 && answer.length < k; c--) {
        for (const value of buckets[c]) {
            answer.push(value);
            if (answer.length === k) break;
        }
    }

    return answer;
}

When should you use Non-comparison sort (counting / radix)?

Use Non-comparison sort (counting / radix) when the problem statement says “keys are integers in a small known range”, “sort ages, grades, or bounded counts” or “need O(n) and comparisons are the bottleneck”. A solution built on it usually runs in O(n).

• •keys are integers in a small known range
• •sort ages, grades, or bounded counts
• •need O(n) and comparisons are the bottleneck
• •sort by digit or fixed-width key
• •n large but the value range is much smaller than n

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Non-comparison sort (counting / radix) confused with?

Non-comparison sort (counting / radix) is most often confused with Fast sort (merge / quick), Hash set / map, Sort with a custom comparator and Elementary sorts (selection, bubble, insertion).

• Fast sort (merge / quick): No comparison sort can beat n log n. Reading the key steps around that limit entirely.
• Hash set / map: A map counts values too, but it keeps no order. Counting sort uses the value as an index.
• Sort with a custom comparator: A comparator describes the order between two items. Counting sort never looks at two items.
• Elementary sorts (selection, bubble, insertion): Those compare neighbours and cost n squared. Counting sort is linear when the range allows it.

Common mistakes with Non-comparison sort (counting / radix)

• Using it on a huge range of keys

  One counter per key means memory the size of the range. Values up to 1e9 make that impossible.

• An unstable pass inside radix sort

  Each digit pass must preserve the order from the last one. Otherwise earlier work is lost.

• Forgetting negative values

  An array index cannot be negative. Shift every key by the minimum first.

• Counting floats or strings

  The key has to be a bounded integer. Anything else needs a comparison sort.

Which interview problems use Non-comparison sort (counting / radix)?

Interview problems solved with Non-comparison sort (counting / radix) include Sort an array of small integers, Sort colors, Top k frequent elements, H-index, Maximum gap, Relative sort array and Sort characters by frequency.

• Sort an array of small integers: One counter per value, then read them back in order.
• Sort colors: Three possible keys, so three counters.
• Top k frequent elements: The count itself becomes the bucket index.
• H-index: Citation counts, capped at the number of papers.
• Maximum gap: Radix sort is what makes a linear solution possible.
• Relative sort array: Counting sort with an order given by another list.
• Sort characters by frequency: Buckets keyed by how often a letter appears.

What is the time and space complexity of Non-comparison sort (counting / radix)?

The target complexity of Non-comparison sort (counting / radix) is O(n).

n values with keys under k gives O(n + k). Radix sort costs O(d times n) across d digits.