Sorting Algorithms

"Quick sort, merge sort, heap sort, counting sort, radix sort, bucket sort, tim sort, intro sort."

Deep Dive Tutorial

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

lightbulb

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.

Worked Problems

Sort Colors (Dutch National Flag)

Medium

Medium

Hard

Medium

Easy

brain

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

← All Patterns