4.10 — Sorting & Searching

You will almost never write a sort. You will constantly choose one, analyse one, and be asked to explain why the one in your standard library is built the way it is. That last question is more interesting than it sounds, because the answer is "it is three algorithms glued together, and each one is there to cover a specific failure of the others".

1. Binary search, and the three details that break it

Searching a sorted array is the payoff for sorting in the first place. The idea is one line: look at the middle, throw away the half that cannot contain the target, repeat.

function binarySearch(sorted: number[], target: number): number {
  let lo = 0, hi = sorted.length - 1;                  // (1)
  while (lo <= hi) {                                   // (2)
    const mid = lo + ((hi - lo) >> 1);                 // (3)
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;            // (4)
    else hi = mid - 1;
  }
  return -1;                                           // (5)
}

1. An inclusive range: both lo and hi are candidates. The other convention is hi = length with an exclusive upper bound, and mixing the two is where most bugs come from. Pick one and stay in it.
2. <= and not <. With an inclusive range, lo === hi still describes one live candidate, and stopping there misses it.
3. Why not (lo + hi) / 2? On a language with fixed-width integers, lo + hi can overflow past the maximum value and go negative, producing a nonsense index. This bug sat undetected in the Java standard library's binary search for nine years, and in Jon Bentley's Programming Pearls for twenty. lo + (hi - lo) / 2 is the same number and cannot overflow. JavaScript's doubles do not have this problem at realistic sizes, but the habit is worth keeping because you will write other languages.
4. The target is bigger, so everything from mid down is out. mid + 1, not mid — using mid leaves the range unchanged when lo === hi and the loop never ends.
5. Not found.

O(\log n) time, O(1) space. Twenty steps for a million elements, thirty for a billion.

The version you actually need more often is not "find the target" but "find the first position where a condition becomes true". This form has no equality check at all and handles duplicates cleanly:

function lowerBound(sorted: number[], target: number): number {   // (1)
  let lo = 0, hi = sorted.length;                                 // (2)  exclusive
  while (lo < hi) {                                               // (3)
    const mid = lo + ((hi - lo) >> 1);
    if (sorted[mid] < target) lo = mid + 1;                       // (4)
    else hi = mid;                                                // (5)
  }
  return lo;                                                      // (6)
}

1. Returns the index of the first element not less than target — the insertion point that keeps the array sorted.
2. hi is one past the end, because the answer may legitimately be "append at the end".
3. <, matching the exclusive convention.
4. mid is too small to be the answer, so discard it.
5. mid might be the answer, so keep it in the range. This asymmetry is the entire algorithm.
6. When the range is empty, lo is the boundary.

The generalisation worth internalising: binary search does not need an array. It works on any monotonic predicate — any yes/no question whose answer, once it flips from false to true, stays true. "Is this array element at least X" is one such question, but so is "can we finish all shipments in D days with capacity C", "does a rope of length L cut into K pieces", and "is a speed of S fast enough". Chapter 4.11 is built almost entirely on this move, called binary search on the answer: you are not searching a data structure, you are searching a range of possible answers.

2. The O(n^2) sorts, and the one that is still useful

Three simple sorts, all O(n^2), and only one of them earns its place in modern code.

Bubble sort repeatedly swaps adjacent out-of-order pairs. It exists to be taught and should never be used; it does the most swaps of any sort.

Selection sort finds the minimum of the unsorted region and swaps it into place. Always exactly n−1 swaps, which is its one virtue: if a write is far more expensive than a read — as when sorting data in flash memory with limited write cycles — the minimal swap count matters.

Insertion sort takes each element and slides it backwards into its correct position among the already-sorted prefix.

function insertionSort(a: number[]): void {
  for (let i = 1; i < a.length; i++) {
    const value = a[i];                                 // (1)
    let j = i - 1;
    while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; j--; }   // (2)
    a[j + 1] = value;                                   // (3)
  }
}

1. Lift the current element out, leaving a gap.
2. Slide everything larger one slot right. Note it shifts rather than swapping — one write per moved element instead of three.
3. Drop it into the gap.

Insertion sort is genuinely useful, for three reasons.

It is O(n) on nearly-sorted data. If every element is at most k positions from its final home, the inner loop runs at most k times, giving O(nk). On already-sorted input it does one comparison per element and finishes in O(n) — better than merge sort or quicksort, which do their full work regardless.

It has a tiny constant factor and allocates nothing, so on small arrays it beats O(n \log n) sorts outright. The crossover is typically around 10 to 30 elements.

It is stable and online — it can sort data as it arrives, without seeing all of it first.

Both of the first two reasons are why insertion sort is inside every production sort in the world, as the base case for small subarrays.

3. Merge sort: predictable, stable, and it needs the memory

Split in half, sort each half recursively, merge the two sorted halves.

function mergeSort(a: number[]): number[] {
  if (a.length <= 1) return a;                          // (1)
  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));              // (2)
  const right = mergeSort(a.slice(mid));
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const out: number[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);       // (3)  ← `<=` keeps it stable
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);          // (4)
  while (j < right.length) out.push(right[j++]);
  return out;
}

1. One element is already sorted.
2. slice copies, which is where the O(n) extra space comes from. Production implementations pass index ranges into a shared scratch buffer instead.
3. The <= rather than < is what makes merge sort stable. When two elements compare equal, taking from the left half first preserves their original relative order. Changing it to < silently breaks stability, and nothing about the sorted output reveals it.
4. One side runs out first; drain the other.

Chapter 4.1 solved the recurrence: T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n), worst case, best case and average case identical. No input makes it slow.

Stability, and why it matters. A stable sort keeps equal elements in their original relative order. That matters whenever you sort by more than one key: sort employees by name, then by department, and a stable sort leaves each department's employees still in name order. An unstable sort scrambles them, and you have to write a compound comparator instead. This is why Java uses a merge-sort variant for objects and quicksort for primitives — for primitives, two equal integers are indistinguishable, so stability is meaningless and speed wins.

The memory is the real cost. O(n) extra space. In-place merge algorithms exist but are complicated and slower. This is why quicksort tends to be preferred for in-memory arrays, and why merge sort is the only choice for data too big for memory — Chapter 4.16's k-way merge is exactly external merge sort, which sorts chunks that fit in RAM, writes them to disk, and merges the sorted runs.

4. Quicksort: fastest in practice, and the failure everyone should know

Pick a pivot, partition the array so everything smaller is on the left and everything larger on the right, then recurse into both sides. No merge step is needed, because the partition already put the pivot in its final position.

function quickSort(a: number[], lo = 0, hi = a.length - 1): void {
  if (lo >= hi) return;
  const p = partition(a, lo, hi);                       // (1)
  quickSort(a, lo, p - 1);                              // (2)
  quickSort(a, p + 1, hi);
}

function partition(a: number[], lo: number, hi: number): number {
  const pivotIndex = lo + Math.floor(Math.random() * (hi - lo + 1));   // (3)
  [a[pivotIndex], a[hi]] = [a[hi], a[pivotIndex]];
  const pivot = a[hi];

  let write = lo;                                       // (4)
  for (let read = lo; read < hi; read++) {
    if (a[read] < pivot) { [a[write], a[read]] = [a[read], a[write]]; write++; }   // (5)
  }
  [a[write], a[hi]] = [a[hi], a[write]];                // (6)
  return write;
}

1. Partition returns where the pivot ended up.
2. The pivot is now final, so it is excluded from both recursive calls. This is why quicksort needs no combine step.
3. Randomising the pivot is not optional. With a fixed pivot such as "always the last element", already-sorted input produces the worst case every time — and sorted input is extremely common. Randomising means an adversary would have to predict your random numbers rather than merely hand you sorted data.
4. and 5. This is the write-pointer pattern from Chapter 4.2: everything before write is smaller than the pivot, everything between write and read is larger.
5. Swap the pivot into the boundary position, which is exactly where it belongs.

Complexity: O(n \log n) average, O(n^2) worst case when every partition is maximally lopsided. Space is O(\log n) for the recursion — and only if you recurse into the smaller side first and loop on the larger, which caps the stack depth; naive implementations can reach O(n).

So why is it the default, given the worse worst case? Cache behaviour and constant factors. Partitioning is a single linear scan through contiguous memory with no allocation, which is the access pattern CPUs are fastest at. Merge sort allocates and copies; heapsort jumps around the array. Measured on large arrays, quicksort is commonly two to three times faster than heapsort despite similar comparison counts.

The Dutch national flag problem. An array with many duplicates makes plain quicksort degrade, because equal elements all pile into one side. Three-way partitioning splits into < pivot, = pivot, > pivot and recurses only on the outer two. An array of all-identical values then sorts in O(n) instead of O(n^2). Any production implementation does this.

5. What your standard library actually runs

Timsort — Python's sorted, Java's Arrays.sort for objects, Android, Rust's stable sort, and V8's Array.prototype.sort since 2018. Designed by Tim Peters in 2002 on one observation: real data is rarely random. It is full of already-sorted stretches.

Timsort scans for runs — maximal already-ordered stretches, reversing descending ones in place — extends short runs to a minimum length with insertion sort, and then merges the runs with a stack discipline that keeps the merges balanced. On already-sorted input it is O(n): one scan finds a single run and there is nothing to merge. On random input it is O(n \log n). It is stable, and it uses O(n) extra space.

Introsort — C++'s std::sort. Quicksort, plus two safety nets: switch to insertion sort below about 16 elements, and if the recursion depth exceeds roughly 2\log_2 n — the signal that quicksort is hitting its bad case — switch to heapsort for that subrange. The result is quicksort's speed with a hard O(n \log n) worst-case guarantee. It is not stable, which is why C++ also offers stable_sort.

The JavaScript trap worth knowing: [10, 9, 1].sort() returns [1, 10, 9]. With no comparator, sort converts every element to a string and sorts lexicographically, so "10" sorts before "9". Always pass a comparator for numbers: sort((a, b) => a - b).

6. The \Omega(n \log n) lower bound, and how to beat it

No comparison-based sort can be faster than \Omega(n \log n), and the proof is short enough to reproduce.

An algorithm that only compares pairs makes a sequence of yes/no decisions. Draw them as a binary tree: each internal node is a comparison, each branch is an outcome, each leaf is a final ordering. To be correct, the tree must have a leaf for every possible input ordering, and there are n! of those. A binary tree with n! leaves has height at least \log_2(n!). By Stirling's approximation, \log_2(n!) \approx n \log_2 n - 1.44n, which is \Theta(n \log n). The height is the worst-case number of comparisons. Done.

Beating it requires not comparing. Two sorts do:

Counting sort — when keys are integers in a small known range. Count how many of each value, then write them back out in order. O(n + k) for range k, and stable if you accumulate counts and place from the right. Sorting a million ages 0–120 is one pass plus 121 counters.

Radix sort — sort by the least significant digit with a stable counting sort, then the next, and so on. After processing all d digits the array is fully sorted, because each pass preserves the ordering established by earlier passes — which only works because the inner sort is stable. O(d(n+k)), which for fixed-width integers is O(n).

Neither breaks the theorem, because neither compares elements to each other; they use the structure of the keys. And both come with real limits: they need a bounded key range, extra memory proportional to that range, and they cannot sort by an arbitrary comparator. If someone hands you strings and a custom collation order, you are back to comparisons.

What the interviewer will push on

"Why is (lo + hi) / 2 a bug?" Integer overflow on lo + hi in a fixed-width language, which produced a real bug in Java's library for nine years. lo + (hi - lo) / 2 is identical arithmetic that cannot overflow.

"Quicksort is O(n^2) worst case. Why is it the default sort?" Cache locality — partitioning is a linear scan over contiguous memory — plus no allocation. Then name the two mitigations: randomised pivots make the bad case require an adversary rather than merely sorted input, and introsort caps the damage by switching to heapsort past a depth limit.

"What is stability and when does it matter?" Equal elements keep their original order. It matters for multi-key sorting, and it is required for radix sort's correctness. Volunteering that last point is the tell — most candidates know the definition and not the consequence.

"Prove that comparison sorting cannot beat n \log n." The decision-tree argument: n! possible orderings need n! leaves, a binary tree with that many leaves has height \log_2(n!) = \Theta(n \log n), and the height is the worst-case comparison count.

"You have a billion 32-bit integers. Sort them." Radix sort, and say why the lower bound does not apply: it never compares two elements, it uses the digit structure. Then mention the memory: if a billion integers do not fit in RAM, this becomes external merge sort, which is Chapter 4.16's k-way merge.

"Find the k-th smallest element." Not by sorting. Quickselect — quicksort's partition, but recurse into only the side containing k — is O(n) average, as Chapter 4.1 derived from T(n) = T(n/2) + \Theta(n). A heap of size k is O(n \log k) and works on streams. Naming both and saying which fits the constraints is the complete answer.

One thing to volunteer: mention that Timsort exists because real data is not random, and that on nearly-sorted input it is O(n). That reframes sorting from an abstract exercise into a statement about the data you actually have, which is where the engineering is.

Recall

• Binary search needs one convention (inclusive hi with <=, or exclusive with <) held consistently, and lo + (hi - lo) / 2 to avoid integer overflow.
• The more useful form is lower bound — the first index where a monotonic predicate turns true — which generalises to binary search on the answer, where you search a range of candidate answers rather than an array.
• Insertion sort is O(n) on nearly-sorted data, allocates nothing and has a tiny constant, which is why it is the small-array base case inside every production sort.
• Merge sort is \Theta(n \log n) in every case and stable (from the <= in the merge), at O(n) extra space; it is the only option for data larger than memory.
• Quicksort is O(n \log n) average and O(n^2) worst case, and wins in practice on cache locality; randomise the pivot and use three-way partitioning for duplicates.
• Timsort exploits existing runs and is O(n) on sorted input; introsort is quicksort with insertion sort below ~16 elements and heapsort past a depth limit.
• Comparison sorting cannot beat \Omega(n \log n) by the decision-tree argument; counting and radix sort beat it by not comparing, at the cost of needing bounded integer keys — and radix requires a stable inner sort.

Self-test: Why does lo = mid instead of mid + 1 cause an infinite loop? · What exactly makes merge sort stable, and what breaks if you change it? · Why does randomising the pivot help, given the worst case still exists? · Reproduce the n \log n lower-bound proof · Why does radix sort break if its inner sort is unstable?

Next: 4.11 works the seven binary search problems, ending with the move that turns hard-looking optimisation questions into three lines — searching the answer instead of the data.