Sorting & Searching

01Why n log n is the wall (and how to tunnel under it)

Comparison sorting is 20-questions with the data: each comparison yields one bit of information. n elements have n! possible orderings; to identify the true one you need at least log₂(n!) ≈ n log n bits. No comparison sort can beat O(n log n) in the worst case — not cleverness, information theory.

02Merge sort — trust, then merge

The idea: split in half, recursively sort each half (leap of faith — file 07), then merge two sorted lists — which is easy: repeatedly take the smaller head. Two pointers, one pass.

             [38, 27, 43, 3]
             /             \
       [38, 27]           [43, 3]
        /    \             /    \
     [38]   [27]        [43]   [3]     ← log n levels of splitting
        \    /             \    /
       [27, 38]           [3, 43]      ← merge back up: each level touches
             \             /             all n elements once
            [3, 27, 38, 43]              → n work × log n levels = O(n log n)

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps it STABLE (see §4)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out += left[i:] + right[j:]
    return out

Character sheet: worst case O(n log n) guaranteed — no bad inputs, ever. Stable. Costs O(n) extra memory. Predictability is its brand — and because it consumes data as sequential streams, it's the backbone of external sorting: sorting data too big for RAM by merging sorted runs from disk. This is what a database does for a huge ORDER BY that spills — Postgres literally reports "external merge" in EXPLAIN ANALYZE.

03Quicksort — partition, then trust

Merge sort does its work after the recursive calls (merging); quicksort does its work before (partitioning). Pick a pivot, sweep once moving everything smaller to its left and everything bigger to its right — now the pivot is in its final resting place, and the two sides can be sorted independently. No merge needed.

        [3, 8, 2, 5, 1, 4]    pivot = 4
   partition → [3, 2, 1] [4] [8, 5]
                         ▲
                 4 is DONE — final position
        recurse left        recurse right

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)

def partition(a, lo, hi):
    r = random.randint(lo, hi)             # randomized pivot — the safety line
    a[r], a[hi] = a[hi], a[r]
    pivot, write = a[hi], lo
    for i in range(lo, hi):                # Lomuto: writer collects the "smalls"
        if a[i] < pivot:
            a[i], a[write] = a[write], a[i]
            write += 1
    a[write], a[hi] = a[hi], a[write]      # drop pivot into its slot
    return write

Character sheet: average O(n log n) with small constants, in-place (O(log n) stack only), not stable.

The spinoff that matters — Quickselect

To find the k-th smallest, partition and recurse into only the side containing k. Expected O(n) — the work shrinks geometrically: n + n/2 + n/4 + ... = 2n. This is the "Kth Largest Element without sorting" answer (alongside the size-k min-heap version, O(n log k) — file 06).

04Heapsort, stability, and the comparison-sort scoreboard

Heapsort in one breath: heapify the array in place (O(n), file 06), then extract-max n times, parking each max in the shrinking tail — O(n log n) worst case, O(1) extra space, not stable. It's the guaranteed-bound, no-extra-memory option with worse constants than quicksort (cache-hostile jumps). Its cameo in the real world: C++ introsort = quicksort that switches to heapsort if recursion gets suspiciously deep — best average case and guaranteed worst case.

Stability — the sleeper interview topic

A sort is stable if equal keys keep their original relative order. Why you care: multi-key sorting by successive passes. Sort employees by name, then stable-sort by department ⇒ departments grouped, names alphabetical within each. It's ORDER BY dept, name built from two passes — and it only works because the second sort didn't scramble the first. Python's sort is stable, and the docs bless exactly this idiom.

(Asha,  Infra)
(Bo,    ML)
(Chen,  Infra)
(Devi,  ML)     # names now alphabetical

(Asha,  Infra)  # Infra group: Asha before Chen —
(Chen,  Infra)  # pass 1's order SURVIVED the tie
(Bo,    ML)     # ML group: still alphabetical
(Devi,  ML)     # = ORDER BY dept, name

An unstable second pass could emit Chen before Asha inside Infra — the name ordering you paid for in pass 1 would be scrambled on equal keys.

05Non-comparison sorts: cheating with key knowledge

Counting sort — keys are integers in a small range [0, k): count occurrences, then replay the counts in order. O(n + k), stable (in the prefix-sum formulation).

def counting_sort(a, k):                 # values in 0..k-1
    counts = [0] * k
    for x in a:
        counts[x] += 1
    out = []
    for v in range(k):
        out.extend([v] * counts[v])
    return out

a = [3, 1, 3, 0, 1]  →  counts [1, 2, 0, 2]  →  [0, 1, 1, 3, 3]
      no comparisons happened — we used the values AS indexes

Sorting a million HTTP status codes? k ≈ 500 ⇒ O(n). Sorting bytes, ages, grades, enum values — counting sort territory. (You've already used this idea: the 26-slot anagram counter in file 02.)

Radix sort — big integers / fixed-length strings: counting-sort by the least significant digit, then the next, ... Stability is what makes it correct: each pass preserves the order established by previous passes. O(d · (n + b)) for d digits in base b.

Bucket sort — uniformly distributed floats: scatter into n buckets, sort each tiny bucket, concatenate. Average O(n); degrades if the distribution clumps.

06Timsort — what sorted() actually does

Python's built-in sort (also Java's objects sort, Rust's stable-sort ancestry) is Timsort: merge sort engineered around one observation — real-world data is rarely random. Logs are nearly time-ordered; you're re-sorting a list that was sorted before the append.

• Scan for runs — stretches already ascending (or descending → reverse in place, O(n/2) swaps).
• Runs shorter than ~32–64 elements are extended via binary insertion sort (small-n constants beat asymptotics — file 01 Q7 made flesh).
• Merge runs with a stack of pending runs and invariants that keep merges balanced; galloping mode exploits one run dominating.

Net effect: worst case O(n log n), stable — but O(n) on already-sorted, reversed, or piecewise-sorted data.

07Sort visualizer — see the comparisons happen

What the counter teaches: insertion sort on random data does ~n²/4 comparisons (each element walks halfway back on average), but on nearly-sorted data almost every element is already in place — one comparison and done, ~O(n) total. Timsort's whole design is "find the parts where that's true (runs), insertion-sort the small gaps, merge the runs."

08Binary search — the idea, the template, the disguises

The idea, properly stated

Binary search does not require "a sorted array." It requires a monotonic predicate: a yes/no question over an ordered domain that flips once — N N N N Y Y Y — and never flips back. Sorted-array lookup is just the special case where the predicate is a[i] >= target. State it this way and every "disguise" becomes the same problem: find the first Y.

index:      0   1   2   3   4   5   6   7
predicate:  N   N   N   Y   Y   Y   Y   Y
                        ▲
                  find this boundary in O(log n)

The bug-free template (memorize exactly one)

Off-by-one bugs come from mixing conventions. Fix one convention and reuse it forever:

def first_true(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) True; hi+1 if none.
    Invariant: answer is always inside [lo, hi]."""
    while lo < hi:                    # strict <  (no <=)
        mid = (lo + hi) // 2          # mid rounds LOW → mid < hi always
        if pred(mid):
            hi = mid                  # mid could be the answer → keep it
        else:
            lo = mid + 1              # mid is a N → discard it
    return lo                         # lo == hi == the boundary

Why it can't infinite-loop or skip the answer: mid is always < hi, so hi = mid strictly shrinks; lo = mid + 1 strictly shrinks; the answer is never discarded (we only drop confirmed Ns, and keep candidate Ys). Loop ends with lo == hi = first Y. Three decisions, made once, never re-derived under pressure: while lo < hi, hi = mid, lo = mid + 1.

Everything reduces to first_true:

# classic lookup: first index where a[i] >= target, then check equality
i = first_true(0, len(a), lambda m: a[m] >= target)     # == bisect_left!
found = i < len(a) and a[i] == target

# last N variant ("last index where a[i] <= target") = first_true(...) - 1

And in real code, don't hand-roll at all: bisect.bisect_left(a, target) is this function (file 09).

The disguises (ranked by interview frequency)

09Common interview questions

10Self-test

1. Reproduce the comparison-sort lower bound argument in two sentences.
2. Merge sort: where does the log come from, where does the n come from, and which single character in the merge makes it stable?
3. Walk Lomuto partition on [3, 8, 2, 5, 1, 4] with pivot 4 — show the array after each swap.
4. Quickselect: why is it expected O(n) and not O(n log n)? (What does it not do that quicksort does?)
5. Fill in the scoreboard from memory: worst case / space / stability for merge, quick, heap.
6. When is counting sort applicable, what's its complexity, and why does radix sort require a stable inner sort?
7. Describe Timsort in ≤ 3 sentences, including the word "runs" and the small-n trick.
8. Write first_true from memory. Justify each of the three decisions (loop condition, hi branch, lo branch) against infinite loops and lost answers.
9. Express "count occurrences of x in a sorted array" using two bisects.
10. For each, name the binary-search disguise: (a) first failing build in CI history, (b) min capacity to ship packages in D days, (c) find minimum in rotated array, (d) find x in a sorted matrix.