Sorting Algorithms & Applications

"Non-comparison sorts beat O(n log n). Sorting enables patterns: binary search, two pointers."

Sorting is the most-used preprocessing step. Comparison-based sorts (merge, heap) are O(n log n). Non-comparison sorts (counting, radix, bucket) can be O(n). But more important than the algorithms themselves: recognizing when sorting enables a more efficient approach to the actual problem.

16 min readdp problems →

Problems you can solve with this pattern

5 problems · click any to start solving

All dp →

1Sort Colors (Dutch National Flag)MediumSolve

2Largest NumberMediumSolve

3Maximum GapHardSolve

4H-IndexMediumSolve

Counting sort, radix sort, bucket sort

// COUNTING SORT: O(n + k) for integers in [0, k-1]
function countingSort(arr, k) {
    const count = new Array(k).fill(0);
    for (const x of arr) count[x]++;
    // Build prefix sums for stable sort
    for (let i = 1; i < k; i++) count[i] += count[i-1];
    const result = new Array(arr.length);
    for (let i = arr.length-1; i >= 0; i--) result[--count[arr[i]]] = arr[i];
    return result;
}

// RADIX SORT: O(d × n) where d = number of digits
function radixSort(arr) {
    const max = Math.max(...arr);
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10)
        arr = countingSortByDigit(arr, exp);
    return arr;
}
function countingSortByDigit(arr, exp) {
    const count = new Array(10).fill(0);
    for (const x of arr) count[Math.floor(x/exp)%10]++;
    for (let i = 1; i < 10; i++) count[i] += count[i-1];
    const result = new Array(arr.length);
    for (let i = arr.length-1; i >= 0; i--) {
        const d = Math.floor(arr[i]/exp)%10;
        result[--count[d]] = arr[i];
    }
    return result;
}

// BUCKET SORT: O(n) average for uniform distribution
function bucketSort(arr, bucketSize = 5) {
    if (!arr.length) return arr;
    const [min, max] = [Math.min(...arr), Math.max(...arr)];
    const buckets = Array.from({length: Math.floor((max-min)/bucketSize)+1}, ()=>[]);
    for (const x of arr) buckets[Math.floor((x-min)/bucketSize)].push(x);
    return buckets.flatMap(b => b.sort((a,b) => a-b));
}

Every sorting interview question has two layers: (1) do you know the algorithm, and (2) can you use sorting as a preprocessing step to solve the real problem? Most interview sorting questions are really about the second layer. "Sort by X then use greedy/two-pointer/binary-search" is the actual pattern.

Algorithm	Time	Space	Stable?	When to use
Merge Sort	O(n log n)	O(n)	Yes	Count inversions, external sort
Quick Sort	O(n log n) avg	O(log n)	No	In-place, fast in practice
Heap Sort	O(n log n)	O(1)	No	In-place, guaranteed O(n log n)
Counting Sort	O(n + k)	O(k)	Yes	Small integer range [0, k]
Radix Sort	O(d × (n + k))	O(n + k)	Yes	Multi-digit integers
Bucket Sort	O(n) avg	O(n)	Yes	Uniformly distributed floats
Topological Sort	O(V + E)	O(V)	N/A	DAG dependency ordering

Non-Comparison Sort Templates

Counting sort, radix sort, bucket sort

// COUNTING SORT: O(n + k) for integers in [0, k-1]
function countingSort(arr, k) {
    const count = new Array(k).fill(0);
    for (const x of arr) count[x]++;
    // Build prefix sums for stable sort
    for (let i = 1; i < k; i++) count[i] += count[i-1];
    const result = new Array(arr.length);
    for (let i = arr.length-1; i >= 0; i--) result[--count[arr[i]]] = arr[i];
    return result;
}

// RADIX SORT: O(d × n) where d = number of digits
function radixSort(arr) {
    const max = Math.max(...arr);
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10)
        arr = countingSortByDigit(arr, exp);
    return arr;
}
function countingSortByDigit(arr, exp) {
    const count = new Array(10).fill(0);
    for (const x of arr) count[Math.floor(x/exp)%10]++;
    for (let i = 1; i < 10; i++) count[i] += count[i-1];
    const result = new Array(arr.length);
    for (let i = arr.length-1; i >= 0; i--) {
        const d = Math.floor(arr[i]/exp)%10;
        result[--count[d]] = arr[i];
    }
    return result;
}

// BUCKET SORT: O(n) average for uniform distribution
function bucketSort(arr, bucketSize = 5) {
    if (!arr.length) return arr;
    const [min, max] = [Math.min(...arr), Math.max(...arr)];
    const buckets = Array.from({length: Math.floor((max-min)/bucketSize)+1}, ()=>[]);
    for (const x of arr) buckets[Math.floor((x-min)/bucketSize)].push(x);
    return buckets.flatMap(b => b.sort((a,b) => a-b));
}

Sorting as Preprocessing

When sorting enables a better algorithm:
- Sort → binary search: O(n log n) sort + O(log n) query vs O(n) scan
- Sort → two pointers: find pairs/triples, remove duplicates
- Sort by end time → greedy interval scheduling
- Sort by weight → Kruskal's MST / Huffman coding
- Sort + stack → next greater/smaller element in O(n)

Sorting costs O(n log n). If it enables O(n) or O(n log n) follow-up, it's worth it.

Sort Colors (Dutch National Flag)

Medium

Medium

Hard

Medium

Easy

Sorting algorithm selection:
- General purpose → merge sort (stable) or Array.sort() (V8 uses TimSort)
- Small integer range [0, k] → counting sort O(n+k)
- Large integers, many passes → radix sort O(dn)
- Uniformly distributed floats → bucket sort O(n) average
- 3-way partition → Dutch National Flag (3 pointers)
- Custom order → sort with comparator function

Sort as preprocessing trigger:
- "Largest/smallest after rearranging" → custom comparator
- "Group/pair by property" → sort by property, scan for groups
- "Maximum gap" → bucket sort enables O(n)
- "Median/quantile" → quickselect or partial sort

← Palindrome Patterns Bipartite Graphs & Matching →