Non-comparison sort (counting / radix)

O(n)

Skip comparisons entirely: counting sort tallies how many of each small integer key appear, radix sort sorts digit by digit, both landing at O(n) instead of O(n log n).

Signals

keys are integers in a small known rangesort ages, grades, or bounded countsneed O(n) and comparisons are the bottlenecksort by digit or fixed-width keyn large but the value range is much smaller than n

Template

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;
}

Looks similar, isn't

Fast sort (merge/quick): Comparison sorts can never beat O(n log n) in the worst case, that's a proven lower bound. Counting/radix only beat it because they exploit small-range integer keys instead of comparing elements; without that structure you're back to merge/quicksort.

keys are integers bounded by k, and k is O(n) or smaller -> O(n + k) time, O(n + k) space. A stated small/known key range (not just "n is large") is the cue over a general comparison sort.

Learn this pattern