Pattern GuideSorting

Sorting

"Bringing order to chaos — O(N log N) at a time."

10 min read Foundation Ω(N log N) comparison lower bound
01
CORE INTUITION

The Guarantees of Order

Sorting is rarely the goal — it's the precondition that unlocks faster algorithms. Once data is sorted, three structural guarantees emerge:

🎯

Binary Search

O(log N) lookup instead of O(N). Sorting once pays for itself after ~log N searches.

🔗

Neighbor Guarantees

Duplicates are adjacent. The K-th element is at index K. Ranges become contiguous.

📐

Two-Pointer Ready

Sorted arrays enable O(N) two-pointer passes for pair sums, merging, partitioning.

02
THEORY

Why O(N log N) is the Floor

🌳

The Decision Tree Argument

Any comparison-based sort can be modeled as a binary decision tree. Each comparison (a < b?) has two outcomes — the tree has at most 2^h leaves. To distinguish all N! permutations, we need 2^h ≥ N!. By Stirling's approximation:

h ≥ log₂(N!) ≈ N log₂ N — 1.44N

This is not an implementation limit — it's a mathematical limit. No comparison sort can beat O(N log N). Merge Sort, Quick Sort, and Heap Sort all achieve this bound. The differences are in constants, stability, and memory.

Escape hatch: Non-comparison sorts (Counting, Radix, Bucket) exploit structure in the data — bounded ranges, fixed digit length — to bypass the decision tree entirely and achieve O(N).

03
SPECTRUM

Three Regimes of Sorting

What does "stable" mean?

A stable sort keeps equal-key elements in their original relative order. Sort [(5,A), (3,B), (5,C)] by number: a stable sort gives [(3,B), (5,A), (5,C)] — A still comes before C, exactly as they started. An unstable sort could just as easily produce [(3,B), (5,C), (5,A)]. It matters whenever you sort by one key after already sorting by another (e.g., sort rows by last name, then stably re-sort by department — names stay alphabetical within each department).

O(N²) — Elementary Sorts

Insertion Sort is the practical O(N²) sort. It's O(N) on nearly-sorted data (adaptive) and uses no extra space. Python's TimSort and Java's Dual-Pivot QuickSort both fall back to insertion sort for tiny subarrays (N < 47 or so).

Key insight: Despite being O(N²) worst-case, insertion sort beats O(N log N) sorts on small arrays due to lower constant factors and cache friendliness.

O(N log N) — Comparison Sorts

Three canonical algorithms, each with a distinct trade-off:

Merge Sort

Stable ✓, O(N) extra space, guaranteed O(N log N). Best for linked lists and external sorting.

Quick Sort

In-place ✓, Unstable, O(N²) worst-case (rare with good pivot). Fastest in practice on arrays.

Heap Sort

In-place ✓, Unstable, guaranteed O(N log N). No worst-case degradation but poor cache locality.

04
CODE

Merge Sort + Quick Sort + Counting Sort

Merge Sort — "Divide, Conquer, Combine"

The canonical O(N log N) algorithm. Split the array in half, sort each half recursively, then merge the two sorted halves in linear time. Stable, guaranteed O(N log N), O(N) memory.

38
27
43
3
Original

Start with one unsorted array of 4 elements.

1 / 11
merge_sort.js
1
function mergeSort(arr) {
2
if (arr.length < 2) return arr;
3
const mid = Math.floor(arr.length / 2);
4
const left = mergeSort(arr.slice(0, mid));
5
const right = mergeSort(arr.slice(mid));
6
return merge(left, right);
7
}
8
9
function merge(left, right) {
10
const res = [];
11
let i = 0, j = 0;
12
while (i < left.length && j < right.length) {
13
if (left[i] <= right[j]) res.push(left[i++]);
14
else res.push(right[j++]);
15
}
16
return [...res, ...left.slice(i), ...right.slice(j)];
17
}

Quick Sort

Partition → recurse. In-place, fast average-case.

quick_sort.js
1
function quickSort(arr, low = 0, high = arr.length - 1) {
2
if (low < high) {
3
const p = partition(arr, low, high);
4
quickSort(arr, low, p - 1);
5
quickSort(arr, p + 1, high);
6
}
7
}
8
9
function partition(arr, low, high) {
10
const pivot = arr[high];
11
let i = low;
12
for (let j = low; j < high; j++) {
13
if (arr[j] < pivot) {
14
[arr[i], arr[j]] = [arr[j], arr[i]];
15
i++;
16
}
17
}
18
[arr[i], arr[high]] = [arr[high], arr[i]];
19
return i;
20
}

Counting Sort

Count → reconstruct. O(N + K) where K is the value range.

counting_sort.js
1
function countingSort(arr) {
2
const max = Math.max(...arr);
3
const min = Math.min(...arr);
4
const range = max - min + 1;
5
const count = new Array(range).fill(0);
6
7
for (const x of arr) count[x - min]++;
8
9
let idx = 0;
10
for (let i = 0; i < range; i++) {
11
while (count[i] > 0) {
12
arr[idx++] = i + min;
13
count[i]--;
14
}
15
}
16
return arr;
17
}
05
LANGUAGES

What Your Language Actually Uses

JavaScript (Array.sort)

TimSort (stable, adaptive merge + insertion). O(N log N) guaranteed.

Python (list.sort)

TimSort (same inventor). O(N) on nearly-sorted data. The gold standard for real-world sorting.

Java (Arrays.sort)

Dual-Pivot QuickSort for primitives, TimSort for objects. Dual-pivot reduces swaps ~20%.

C++ (std::sort)

Introsort (QuickSort → HeapSort fallback). O(N log N) guaranteed, in-place.

06
ANTI-PATTERN

When Sorting is the Wrong Answer

Finding the max/min

O(N) scan beats O(N log N) sort + O(1) lookup. Don't sort to find a single extreme.

Quickselect (K-th smallest)

O(N) average with Quickselect. Don't sort the whole array just to find one element's rank.

Hash map lookups

If you only need existence checks or frequency counts, a hash map is O(N) and avoids sorting entirely.

07
SPECIALIZED

Cyclic Sort & Bucket Sort

These two don't fit the comparison/non-comparison regime neatly. They target specific problem patterns and are common interview weapons.

Cyclic Sort — "Every Value Has a Home"

Pattern: You have an array of N elements where the values are in a contiguous range [1, N] (or [0, N-1]). The correct position for value v is index v - 1.

The algorithm scans left to right. If the current element isn't at its correct index, swap it there. Repeat until the current position holds the right value, then advance.

When to reach for it

  • Find the missing number in [0, N]
  • Find all duplicates in an array
  • Find first missing positive integer
  • Find the corrupt pair (duplicate + missing)

Visual walkthrough: [3, 1, 5, 4, 2]

i=0: 3 → belongs at idx 2 → swap → [5, 1, 3, 4, 2]
i=0: 5 → belongs at idx 4 → swap → [2, 1, 3, 4, 5]
i=0: 2 → belongs at idx 1 → swap → [1, 2, 3, 4, 5]
i=0: 1 → belongs at idx 0 → advance → i=1: 2 → advance → ... done

Cyclic Sort — Standard Template

cyclic_sort.js
1
function cyclicSort(nums) {
2
let i = 0;
3
while (i < nums.length) {
4
const correctIdx = nums[i] - 1;
5
if (nums[i] !== nums[correctIdx]) {
6
[nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
7
} else {
8
i++;
9
}
10
}
11
}
12
13
// Variation: Find the missing number (nums[i] ranges [0, N])
14
function findMissing(nums) {
15
let i = 0;
16
while (i < nums.length) {
17
const correctIdx = nums[i];
18
if (nums[i] < nums.length && nums[i] !== nums[correctIdx]) {
19
[nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
20
} else {
21
i++;
22
}
23
}
24
for (let j = 0; j < nums.length; j++) {
25
if (nums[j] !== j) return j;
26
}
27
return nums.length;
28
}

Complexity

Time: O(N) — each swap places at least one element at its correct index, and each element is visited at most twice.
Space: O(1) — purely in-place swaps. No extra memory.

Bucket Sort — "Divide, Sort Individually, Concat"

Pattern: Distribute elements into k buckets based on a mapping function (usually floor(value × k / max)), sort each bucket individually (often Insertion Sort, since each bucket is small), then concatenate.

Bucket Sort achieves O(N) when the data is uniformly distributed across the range. Each bucket ends up with ~N/k elements, and sorting each bucket costs O((N/k)²) with Insertion Sort — which becomes O(N) when k ≈ N.

When to reach for it

  • Sort floating-point numbers uniformly distributed in [0, 1)
  • Sort large datasets with known distribution
  • External sorting (data too large for memory)
  • Top K frequent elements (bucket by frequency)

Visual walkthrough: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] with 5 buckets

Bucket 0 [0, 0.2): 0.17, 0.12 → sorted: [0.12, 0.17]
Bucket 1 [0.2, 0.4): 0.39, 0.26, 0.21, 0.23 → sorted: [0.21, 0.23, 0.26, 0.39]
Bucket 2 [0.4, 0.6): ∅
Bucket 3 [0.6, 0.8): 0.78, 0.72, 0.68 → sorted: [0.68, 0.72, 0.78]
Bucket 4 [0.8, 1.0): 0.94 → sorted: [0.94]
Result: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94] ✓

Bucket Sort — Standard Template

bucket_sort.js
1
function bucketSort(arr, bucketCount = 5) {
2
if (arr.length < 2) return arr;
3
4
const min = Math.min(...arr);
5
const max = Math.max(...arr);
6
const range = (max - min) / bucketCount || 1;
7
8
// Create empty buckets
9
const buckets =
10
Array.from({ length: bucketCount }, () => []);
11
12
// Distribute elements into buckets
13
for (const x of arr) {
14
const idx = Math.floor((x - min) / range);
15
buckets[Math.min(idx, bucketCount - 1)].push(x);
16
}
17
18
// Sort each bucket and concatenate
19
return buckets.flatMap(b => b.sort((a, b) => a - b));
20
}
21
22
// Richer example: Top K frequent elements
23
function topKFrequent(nums, k) {
24
const freq = new Map();
25
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
26
27
// bucket index = frequency
28
const buckets = Array.from(
29
{ length: nums.length + 1 }, () => []
30
);
31
for (const [num, count] of freq) buckets[count].push(num);
32
33
const res = [];
34
for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
35
for (const num of buckets[i]) {
36
res.push(num);
37
if (res.length === k) break;
38
}
39
}
40
return res;
41
}

Complexity & Caveats

Best / Average case: O(N + K) with uniform distribution. Each bucket has O(N/K) elements; sorting all buckets costs K × O((N/K)²) = O(N²/K). When K ≈ N, this simplifies to O(N).
Worst case: O(N²) — all elements land in one bucket (poor distribution or degenerate mapping function).
Space: O(N + K) — the buckets collectively hold all elements.
Stable: Yes, if the per-bucket sort is stable (e.g., stable Insertion Sort).

Compared to Counting Sort & Radix Sort: Counting Sort requires a tiny integer range. Radix Sort needs fixed digit length. Bucket Sort handles floats, arbitrary distributions, and large ranges — it trades worst-case guarantees for flexibility.

08
PITFALLS

Common Mistakes

JavaScript's Default Comparator

[10, 9, 1].sort() gives [1, 10, 9] — with no comparator, JS sorts elements as strings, lexicographically. For numbers, always pass (a, b) => a - b.

Sorting When Something Cheaper Answers

If you only need the max/min, the K-th smallest, or an existence check, a full O(N log N) sort is wasted work — see the "When Sorting is the Wrong Answer" section above.

Comparator Returning a Boolean

Comparators must return a number (negative, zero, or positive) — not true/false. A predicate-style comparator silently produces a wrong or unstable order instead of an error.

Mutating While Sorting

Array.prototype.sort and Python's list.sort() mutate in place. If another reference to the same array is in use elsewhere, sort a copy instead: [...arr].sort(...) or sorted(list).

09
PRACTICE

Ready to Practice?

Bubble SortEasy
Quick SortMedium
Merge SortMedium

"Sorting is a precondition, not a goal. The decision tree proves you can't beat N log N with comparisons alone."