🔃 Sorting

A learning sheet — you'll rarely write a sort, but you must know each one's guarantees, the divide-and-conquer subroutines, and the meta-move: "sort first, and the problem collapses."

🧠 1 · How to think (and invent it)

Sorting wears two hats. Hat 1 — the toolbox: the library sorts in O(n log n), so you usually just call it — but you must know which sort it uses and its guarantees (stable? in-place? worst case?), because those decide correctness. Hat 2 — the weapon: a huge class of problems isn't "sort," but becomes trivial once sorted — enabling two pointers, greedy, sweep lines, or a custom comparator.

Underneath the named algorithms sit three reusable subroutines that show up as building blocks far beyond sorting: the merge (combine two sorted runs), the partition (split around a pivot), and quickselect (find the k-th element without fully sorting).

Watch it get invented — Merge Sort (divide & conquer)

1. Start brute. Insertion/selection sort is O(n²) — every element compared against many others.
2. The leap. Split the array in half, sort each half (recursively), then notice: two already-sorted halves can be stitched into one sorted whole in a single linear pass — the merge step (a two-sequence two-pointer).
3. The recurrence. T(n) = 2·T(n/2) + O(n) → O(n log n). Log levels of halving, each level doing O(n) of merging.
4. Payoff. Guaranteed O(n log n), and stable (keep <= in the merge) — the cost is O(n) extra space.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

§4.1–4.3 are the divide-and-conquer trio (merge, partition, select). §4.4–4.5 are the "beat or avoid the sort" moves. Each: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · Merge sort

“Sort each half, then zip the two sorted runs together.”

function mergeSort(a: number[]): number[] {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}
// the merge step IS a two-sequence two-pointer
function merge(a: number[], b: number[]): number[] {
  const out: number[] = []; let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]); // <= → stable
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

4.2 · Quicksort & partition

“Pick a pivot, shove smaller-left / bigger-right, recurse on each side.”

Setup: the partition is the reusable jewel — it places the pivot at its final sorted index and returns it. Quicksort just recurses on both sides; quickselect (§4.3) recurses on one.

function quickSort(a: number[], lo = 0, hi = a.length - 1): void {
  if (lo >= hi) return;
  const p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
}
// Lomuto partition; randomize the pivot to dodge the O(n²) worst case
function partition(a: number[], lo: number, hi: number): number {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];          // random pivot → swap to the end
  const pivot = a[hi]; let i = lo;
  for (let j = lo; j < hi; j++) if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}

4.3 · Quickselect — the k-th without sorting

“Partition, then recurse into only the side that holds k.”

Setup: a full sort is wasteful if you only need rank k. After a partition, the pivot's final index tells you which side k is on — keep only that side.

// k-th SMALLEST (0-indexed k); for k-th largest use a.length-1-k
function quickselect(a: number[], k: number): number {
  let lo = 0, hi = a.length - 1;
  while (true) {
    const p = partition(a, lo, hi);   // same partition as §4.2
    if (p === k) return a[p];
    if (p < k) lo = p + 1;            // k is to the right
    else hi = p - 1;                  // k is to the left
  }
}

4.4 · Non-comparison (linear) sorts

“Bounded integer keys? Count them — no comparisons, O(n).”

Setup: comparison sorts are stuck at Ω(n log n). If keys are integers in a small range, you can tally instead of compare and beat that bound.

// Counting sort — keys in [0, maxVal]; O(n + maxVal)
function countingSort(a: number[], maxVal: number): number[] {
  const count = new Array(maxVal + 1).fill(0);
  for (const x of a) count[x]++;
  const out: number[] = [];
  for (let v = 0; v <= maxVal; v++) while (count[v]-- > 0) out.push(v);
  return out;
}

4.5 · Sort-as-preprocessing (the meta-move)

“The problem isn't sorting — but sorting makes it fall over.”

Setup: sorting imposes order, which unlocks linear follow-ups: two pointers, greedy-by-order, sweep lines, grouping, or a custom comparator that defines the order you actually need.

// Largest Number — order so that concatenation is biggest (custom total order)
function largestNumber(nums: number[]): string {
  const s = nums.map(String).sort((x, y) => (y + x).localeCompare(x + y)); // "x then y" vs "y then x"
  return s[0] === '0' ? '0' : s.join('');   // all zeros → "0"
}

⏱️ 5 · The sort table

⚠️ 6 · Pitfalls — and the test that catches each

// 41 First Missing Positive — cyclic sort: put v at index v-1
function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1, tmp = nums[i];          // temp swap — [nums[i], nums[nums[i]-1]] = ... reads the modified nums[i]
      nums[i] = nums[j]; nums[j] = tmp;
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

// 853 Car Fleet — sort by position (closest to target first), compare arrival times
function carFleet(target: number, position: number[], speed: number[]): number {
  const cars = position.map((p, i) => [p, (target - p) / speed[i]]).sort((a, b) => b[0] - a[0]);
  let fleets = 0, lead = 0;
  for (const [, t] of cars) if (t > lead) { fleets++; lead = t; }   // slower than the fleet ahead → new fleet
  return fleets;
}

// 128 Longest Consecutive Sequence — O(n): only count from sequence HEADS
function longestConsecutive(nums: number[]): number {
  const set = new Set(nums); let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;                    // not a head
    let len = 1; while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

// 448 Find All Numbers Disappeared — mark presence by negating nums[v-1]
function findDisappearedNumbers(nums: number[]): number[] {
  for (const x of nums) { const i = Math.abs(x) - 1; if (nums[i] > 0) nums[i] = -nums[i]; }
  const res: number[] = [];
  nums.forEach((v, i) => { if (v > 0) res.push(i + 1); });
  return res;
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• merge mergeSort + merge (stable)
• quick partition (random pivot) + quickSort
• select quickselect (k-th smallest)
• linear countingSort
• prep a custom comparator (e.g. largestNumber)

For each: state the guarantee (stable? in-place? worst case?) as a comment before the code.