Sorting and searching

Sorting is the most-asked family of algorithm questions, not because anyone writes a sort at work but because it is the cleanest way to test whether you can reason about invariants, recursion, stability and trade-offs. Binary search is the most failed family, because the off-by-one surface is large and the hard version — binary searching the answer rather than an array — looks nothing like the textbook version.

Everything here was executed: 12 sorts in Python and 6 in TypeScript checked against the built-in sort on 8 input shapes, and every binary-search variant checked against bisect or brute force.

Table of contents

• 1. The comparison-sort landscape
• 2. The quadratic sorts
• 3. Merge sort
• 4. Quicksort
• 5. Heapsort
• 6. Non-comparison sorts
• 7. TimSort, and what your language actually runs
• 8. Sorting in practice: comparators and keys
• 9. Selection: quickselect and friends
• 10. Binary search, done correctly
• 11. Binary searching the answer
• 12. The hard binary searches
• 13. Test run
• 14. Interview questions

1. The comparison-sort landscape

Definitions to have precise, because interviewers ask for them:

• Stable: equal elements keep their relative input order. This is what makes multi-key sorting work (sort by the secondary key, then by the primary).
• In place: O(1) auxiliary space. Quicksort is conventionally called in place despite its O(log n) recursion stack; heapsort is the only comparison sort that is strictly O(1) and O(n log n) worst case.
• Adaptive: faster on partially sorted input. This is the property that matters most in practice, because real data is usually partly ordered.

The lower bound. Any comparison sort needs Omega(n log n) comparisons in the worst case: a comparison sort is a decision tree, each of the n! permutations needs its own leaf, and a binary tree with n! leaves has height at least log2(n!) = Theta(n log n) by Stirling. Counting and radix sorts beat it only because they are not comparison sorts — they read the structure of the keys.

2. The quadratic sorts

They matter for three reasons: insertion sort is what every real sort switches to for small subarrays, the invariants are the simplest place to practice reasoning about loops, and interviewers use them to check whether you know why they lose.

def bubble(a):
    a = a[:]; n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):                      # the last i elements are already final
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]; swapped = True
        if not swapped: break                            # early exit -> O(n) on sorted input
    return a

def selection(a):
    a = a[:]; n = len(a)
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]: m = j
        a[i], a[m] = a[m], a[i]                          # exactly n-1 swaps, always
    return a

def insertion(a):
    a = a[:]
    for i in range(1, len(a)):
        cur = a[i]; j = i - 1
        while j >= 0 and a[j] > cur:                     # shift, do not swap: one write per step
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = cur
    return a

def shell(a):
    a = a[:]; n = len(a); gap = 1
    while gap < n // 3: gap = 3 * gap + 1                # Knuth sequence: 1, 4, 13, 40, 121...
    while gap:
        for i in range(gap, n):                          # gap-insertion sort
            cur = a[i]; j = i
            while j >= gap and a[j - gap] > cur: a[j] = a[j - gap]; j -= gap
            a[j] = cur
        gap //= 3
    return a

Insertion sort is O(n + d) where d is the number of inversions, which is why it is genuinely the fastest option for small or nearly-sorted arrays, and why V8’s TimSort, CPython’s Timsort, and C++‘s introsort all fall back to it. Note the implementation shifts rather than swapping — one write per element moved instead of three.

Selection sort’s one virtue is worth remembering: it does at most n-1 swaps regardless of input, which matters when a “swap” means an erase-write cycle on flash or a round trip to a server.

3. Merge sort

Intuition

Split, sort each half, merge. The merge is the only real work, and it is a linear two-pointer pass — the single most reused subroutine in this whole guide.

        [38 27 43 3 9 82 10]
        /                  \
   [38 27 43]            [3 9 82 10]
    /      \              /       \
 [38]  [27 43]        [3 9]    [82 10]
          / \          / \       / \
       [27] [43]     [3] [9]  [82] [10]
          \ /          \ /       \ /
        [27 43]       [3 9]    [10 82]
    \      /              \       /
   [27 38 43]            [3 9 10 82]
        \                  /
       [3 9 10 27 38 43 82]

T(n) = 2T(n/2) + Theta(n)  ->  Theta(n log n)   [Master Theorem case 2]

def merge_sort(a):
    if len(a) <= 1: return a[:]
    m = len(a) // 2
    return _merge(merge_sort(a[:m]), merge_sort(a[m:]))

def _merge(l, r):
    out = []; i = j = 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i += 1        # <= is what makes it STABLE
        else:            out.append(r[j]); j += 1
    out.extend(l[i:]); out.extend(r[j:])
    return out

def merge_sort_bu(a):                                     # bottom-up: iterative, no recursion
    a = a[:]; n = len(a); width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            a[i:i + 2 * width] = _merge(a[i:i + width], a[i + width:i + 2 * width])
        width *= 2
    return a

function mergeSort<T>(a: readonly T[], cmp: Cmp<T>): T[] {
  if (a.length <= 1) return [...a];
  const m = a.length >> 1;
  return merge(mergeSort(a.slice(0, m), cmp), mergeSort(a.slice(m), cmp), cmp);
}
function merge<T>(l: T[], r: T[], cmp: Cmp<T>): T[] {
  const out: T[] = []; let i = 0, j = 0;
  while (i < l.length && j < r.length) out.push(cmp(l[i]!, r[j]!) <= 0 ? l[i++]! : r[j++]!);
  while (i < l.length) out.push(l[i++]!);
  while (j < r.length) out.push(r[j++]!);
  return out;
}

The three things to say about merge sort

1. <= in the merge is the stability. Change it to < and equal elements from the right half jump ahead of the left half. Verified: with <=, records [(1,'a'),(0,'b'),(1,'c'),(0,'d'),(1,'e')] sorted by the first field give b d a c e — original order preserved within each key.
2. It is the only O(n log n) sort that is stable and has a guaranteed bound, which is exactly why it (as TimSort) is what CPython and V8 ship.
3. The O(n) space is on arrays, not lists. Merge sorting a linked list is O(1) extra space (you relink instead of copying) and O(log n) for the recursion — which is why “sort a linked list in O(1) space” means “bottom-up merge sort”.

Uses beyond sorting

def count_inversions(a):
    """Merge sort that counts how many pairs are out of order. O(n log n)."""
    def go(xs):
        if len(xs) <= 1: return xs, 0
        m = len(xs) // 2
        l, cl = go(xs[:m]); r, cr = go(xs[m:])
        out, i, j, cross = [], 0, 0, 0
        while i < len(l) and j < len(r):
            if l[i] <= r[j]: out.append(l[i]); i += 1
            else:
                out.append(r[j]); j += 1
                cross += len(l) - i          # every remaining left element is > r[j]
        out.extend(l[i:]); out.extend(r[j:])
        return out, cl + cr + cross
    return go(a)[1]

External sorting is the other one: when the data does not fit in memory, sort chunks that do, write them out, then k-way merge the runs with a heap (heapq.merge in Python). That is the answer to “sort a 100 GB file with 1 GB of RAM”.

4. Quicksort

Intuition

Pick a pivot, partition into (< pivot, pivot, > pivot), recurse on the two sides. No merge step — the work is all in the partition, which is why it is faster in practice than merge sort despite the worse worst case: it is in place, so it has far better cache behaviour.

Lomuto partition, pivot at the end:

  [3 7 8 5 2 1 9 | 4]        i = boundary of the "< pivot" region
   i
  scan j; when a[j] < pivot, swap a[i] and a[j] and advance i
  ...
  [3 2 1 | 4 | 8 5 7 9]      finally swap a[i] with the pivot

def quicksort(a):
    a = a[:]
    def part(lo, hi):
        p = random.randint(lo, hi)                       # RANDOMIZED pivot: kills adversarial input
        a[p], a[hi] = a[hi], a[p]
        pivot = a[hi]; i = lo
        for j in range(lo, hi):
            if a[j] < pivot: a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        return i
    def go(lo, hi):
        while lo < hi:
            p = part(lo, hi)
            if p - lo < hi - p:                          # recurse on the SMALLER side...
                go(lo, p - 1); lo = p + 1                # ...and loop on the larger -> O(log n) stack
            else:
                go(p + 1, hi); hi = p - 1
    go(0, len(a) - 1)
    return a

The while loop with tail-call elimination is not decoration: without it, a worst-case partition gives you O(n) recursion depth and a stack overflow on 1e5 elements (Python’s limit is ~1000 frames). Recursing into the smaller half bounds the depth at log2(n) regardless.

Three-way partition for duplicates

Plain quicksort degrades to O(n^2) on an array of all-equal elements. Dijkstra’s three-way partition fixes it and makes such input O(n):

def quicksort_3way(a):
    a = a[:]
    def go(lo, hi):
        if lo >= hi: return
        pivot = a[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if   a[i] < pivot: a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
            elif a[i] > pivot: a[i], a[gt] = a[gt], a[i]; gt -= 1     # do NOT advance i
            else: i += 1
        go(lo, lt - 1); go(gt + 1, hi)                    # the middle is already in place
    go(0, len(a) - 1)
    return a

The subtlety: when you swap from the gt end you must not advance i, because the element you just swapped in has not been examined. That is the classic off-by-one in this algorithm.

The production version: introsort

function quickSort<T>(a: T[], cmp: Cmp<T>, lo = 0, hi = a.length - 1): T[] {
  while (lo < hi) {
    if (hi - lo < 16) { insertionSort(a, cmp, lo, hi); return a; }   // small-subarray cutoff
    const p = partition(a, cmp, lo, hi);
    if (p - lo < hi - p) { quickSort(a, cmp, lo, p - 1); lo = p + 1; }
    else { quickSort(a, cmp, p + 1, hi); hi = p - 1; }
  }
  return a;
}
function partition<T>(a: T[], cmp: Cmp<T>, lo: number, hi: number): number {
  const mid = (lo + hi) >> 1;                                        // median-of-three pivot
  const order = [lo, mid, hi].sort((x, y) => cmp(a[x]!, a[y]!));
  [a[order[1]!], a[hi]] = [a[hi]!, a[order[1]!]!];
  const pivot = a[hi]!; let i = lo;
  for (let j = lo; j < hi; j++) if (cmp(a[j]!, pivot) < 0) { [a[i], a[j]] = [a[j]!, a[i]!]; i++; }
  [a[i], a[hi]] = [a[hi]!, a[i]!];
  return i;
}

C++‘s std::sort is introsort: quicksort with a median-of-three pivot, an insertion-sort cutoff for small subarrays, and a depth counter that switches to heapsort if recursion exceeds 2·log2(n). That last part is what converts quicksort’s O(n^2) worst case into a guaranteed O(n log n) — a very quotable answer to “how do you make quicksort safe”.

Pitfalls

• A fixed pivot (first or last element) is O(n^2) on sorted input — the most common real-world case. Randomize or use median-of-three.
• Hoare partition (two pointers moving inward) does fewer swaps than Lomuto but has more edge cases; if you write it from memory under pressure, use Lomuto.
• Quicksort is not stable, and cannot cheaply be made stable.
• All-equal input needs the three-way partition.

5. Heapsort

Build a max-heap in O(n), then repeatedly swap the root to the end and sift down over the shrinking prefix. The only comparison sort that is simultaneously O(n log n) worst case and O(1) space.

def heapsort(a):
    a = a[:]; n = len(a)
    def sift(i, size):
        while True:
            big, l, r = i, 2 * i + 1, 2 * i + 2
            if l < size and a[l] > a[big]: big = l
            if r < size and a[r] > a[big]: big = r
            if big == i: return
            a[i], a[big] = a[big], a[i]; i = big
    for i in range(n // 2 - 1, -1, -1): sift(i, n)         # heapify: O(n), not O(n log n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]                        # largest to its final position
        sift(0, end)
    return a

So why is it not the default sort anywhere? Cache behaviour. Sifting jumps between indices i, 2i+1, 4i+3 — a new cache line at nearly every step — whereas quicksort’s partition is two sequential scans and merge sort’s merge is three. Heapsort typically loses to quicksort by 2–3x on real hardware despite identical asymptotics. It is the right answer when you need a guarantee with no extra memory (embedded, real-time), and it is what introsort falls back to.

6. Non-comparison sorts

These beat the Omega(n log n) bound by exploiting key structure. The interview move is to notice when the input has that structure.

def counting_sort(a, lo=None, hi=None):
    """O(n + k) where k is the key range. Stable. The workhorse inside radix sort."""
    if not a: return []
    lo = min(a) if lo is None else lo
    hi = max(a) if hi is None else hi
    cnt = [0] * (hi - lo + 1)
    for x in a: cnt[x - lo] += 1
    for i in range(1, len(cnt)): cnt[i] += cnt[i - 1]      # prefix sums = final positions
    out = [0] * len(a)
    for x in reversed(a):                                   # reversed + decrement = STABLE
        cnt[x - lo] -= 1
        out[cnt[x - lo]] = x
    return out

def radix_sort(a):
    """LSD radix, base 10, handling negatives by sorting magnitudes and reversing."""
    neg = [-x for x in a if x < 0]
    pos = [x for x in a if x >= 0]
    def lsd(xs):
        if not xs: return []
        maxv, exp = max(xs), 1
        while maxv // exp > 0:
            buckets = [[] for _ in range(10)]
            for x in xs: buckets[(x // exp) % 10].append(x)
            xs = [x for b in buckets for x in b]            # concatenation must be stable
            exp *= 10
        return xs
    return [-x for x in reversed(lsd(neg))] + lsd(pos)

def bucket_sort(a):
    """O(n) expected when the input is uniformly distributed; O(n^2) if it all lands in one bucket."""
    if not a: return []
    n = len(a); lo, hi = min(a), max(a)
    if lo == hi: return a[:]
    buckets = [[] for _ in range(n)]
    for x in a:
        buckets[int((x - lo) / (hi - lo) * (n - 1))].append(x)
    return [x for b in buckets for x in insertion(b)]

The stability of the concatenation is the whole correctness argument for LSD radix. Each pass sorts by one digit and must preserve the order established by the previous, less significant digit. Use a stable inner sort (counting sort) or a stable bucket concatenation, or radix sort is simply wrong.

Radix is O(d(n + b)) for d digits and base b. With 32-bit ints and base 256 that is 4 passes — genuinely linear, and radix sort beats std::sort on large integer arrays in practice. The catch is that it needs O(n + b) extra memory and cannot use a custom comparator.

7. TimSort, and what your language actually runs

How TimSort works

1. Find natural runs. Scan left to right for maximal already-sorted ascending runs; a strictly descending run is reversed in place (which is why “reversed input” is also a best case).
2. Extend short runs with insertion sort up to a computed minrun (32–64, chosen so that the number of runs is close to a power of two, which makes the merges balanced).
3. Push runs on a stack and merge while invariants hold — classically |C| > |B| + |A| and |B| > |A|, which keeps merges balanced, only ever merges adjacent runs (hence stability), and bounds the stack at O(log n). CPython 3.11+ replaced this with powersort, which computes each run’s “power” and merges optimally with respect to the run-length distribution.
4. Galloping merge. When one run keeps winning, switch from element-by-element to exponential search for the insertion point, which makes merging two very differently-sized runs sublinear.

Measured adaptivity

list.sort() on 2,000,000 floats, CPython 3.11.15:

input                          seconds   vs random
random                          0.6453        1.0x
already sorted                  0.0697        9.3x
reversed                        0.0640       10.1x
nearly sorted (0.1% swaps)      0.0852        7.6x

Sorted input is 9.3x faster than random, reversed is 10.1x (one reversal, then one run), and even after randomly swapping 0.1% of positions it is still 7.6x. (Re-running on the same machine gave 10.6x / 7.9x / 5.7x — the individual ratios move by a few points run to run on a shared container, but the order of magnitude is stable, and that is the claim.) That is the practical payoff of adaptivity, and it is why “the data is usually nearly sorted” is a legitimate performance argument.

V8’s blog reported up to a 17x speedup on reverse-sorted input when it moved from quicksort to TimSort, for the same reason.

8. Sorting in practice: comparators and keys

The JavaScript default-comparator trap

[10, 9, 1].sort();                  // [1, 10, 9]   <- lexicographic on the STRING form
[10, 9, 1].sort((a, b) => a - b);   // [1, 9, 10]

Verified. Array.prototype.sort with no comparator converts every element with ToString and compares UTF-16 code units. This bites on numbers, on undefined (always sorted to the end regardless of comparator), and on holes (also moved to the end).

// multi-key, descending then ascending
rows.sort((a, b) => b.score - a.score || a.name.localeCompare(b.name));

// locale-correct string sorting — and hoist the Collator, it is expensive to construct
const coll = new Intl.Collator('es', { sensitivity: 'base', numeric: true });
names.sort(coll.compare);

// non-mutating (ES2023)
const sorted = rows.toSorted((a, b) => a.id - b.id);

The || chain works because a comparator returns 0 for “equal”, which is falsy — so it falls through to the next criterion. It is the idiomatic multi-key comparator in JavaScript.

Python keys

rows.sort(key=lambda r: r.score)                      # key is called n times
rows.sort(key=lambda r: (-r.score, r.name))           # descending score, ascending name
rows.sort(key=operator.itemgetter(1))                 # ~30% faster: stays in C
rows.sort(key=operator.attrgetter('score', 'name'))
rows.sort(key=functools.cmp_to_key(legacy_cmp))       # last resort: O(n log n) Python calls

Three points worth making:

• key is evaluated once per element (n calls); a comparator runs O(n log n) times. That is why Python removed cmp in 3.0 and why key= is always preferred.
• Stability enables multi-pass sorting: rows.sort(key=secondary); rows.sort(key=primary) gives you primary-then-secondary ordering without building a tuple. Useful when the secondary key is expensive or when the two sorts happen in different places.
• The (-score, name) tuple trick only works for numeric descending. For a string descending plus something ascending, you need two passes or cmp_to_key.

Interview-favourite sorting problems

# Sort colors / Dutch national flag: 0s, 1s, 2s in one pass, O(1) space
def sort_colors(a):
    lo, i, hi = 0, 0, len(a) - 1
    while i <= hi:
        if   a[i] == 0: a[lo], a[i] = a[i], a[lo]; lo += 1; i += 1
        elif a[i] == 2: a[i], a[hi] = a[hi], a[i]; hi -= 1     # do not advance i
        else: i += 1

# Merge intervals: sort by start, then sweep
def merge_intervals(iv):
    iv = sorted(iv)
    out = []
    for s, e in iv:
        if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
        else: out.append([s, e])
    return out

# Largest number from concatenation: a custom comparator is unavoidable
from functools import cmp_to_key
def largest_number(nums):
    s = sorted(map(str, nums), key=cmp_to_key(lambda x, y: (1 if x + y < y + x else -1)))
    return ''.join(s).lstrip('0') or '0'

# Meeting rooms II: minimum rooms = max concurrent intervals
import heapq
def min_rooms(iv):
    heap = []
    for s, e in sorted(iv):
        if heap and heap[0] <= s: heapq.heappop(heap)
        heapq.heappush(heap, e)
    return len(heap)

# Top k frequent: Counter + heap
def top_k_frequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]        # O(n log k)

“Sort by start” is the single most productive first move in interval problems, and “sort by end” is the right one for interval scheduling (maximize non-overlapping meetings). Knowing which is which is worth memorizing: earliest end time is the greedy that maximizes the count.

9. Selection: quickselect and friends

Finding the kth smallest does not require sorting.

def quickselect(a, k):
    """Expected O(n). Same partition as quicksort, but recurse into only ONE side."""
    a = a[:]; lo, hi = 0, len(a) - 1
    while True:
        if lo == hi: return a[lo]
        p = random.randint(lo, hi); a[p], a[hi] = a[hi], a[p]
        pivot = a[hi]; i = lo
        for j in range(lo, hi):
            if a[j] < pivot: a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        if k == i: return a[i]
        if k < i: hi = i - 1
        else:     lo = i + 1

Why O(n) expected: a random pivot lands in the middle half with probability 1/2, so E[T(n)] = T(3n/4) + O(n), and n + 3n/4 + 9n/16 + … = 4n. Worst case is still O(n^2); median-of-medians makes it O(n) worst case by choosing a provably good pivot (split into groups of 5, take the median of each, recurse to find the median of those), at the cost of a large constant that makes it rarely worth using in practice.

The streaming answer is the one interviewers usually want after quickselect: to keep the top k of an unbounded stream, hold a min-heap of size k, push, and pop when the size exceeds k. The heap’s root is then the kth largest.

10. Binary search, done correctly

graph TD
    A["lo = 0, hi = len(a)"] --> B{"lo < hi?"}
    B -- "no" --> G["return lo"]
    B -- "yes" --> C["m = lo + (hi - lo) // 2"]
    C --> D{"a[m] < target?"}
    D -- "yes" --> E["lo = m + 1<br/>(discard left half)"]
    D -- "no" --> F["hi = m<br/>(discard right half)"]
    E --> B
    F --> B

Binary search is trivial to describe and easy to get wrong. The fix is to pick one template per question type and always write that.

Template A — exact match, inclusive bounds

def bsearch(a, t):
    lo, hi = 0, len(a) - 1            # INCLUSIVE
    while lo <= hi:                   # note <=
        m = lo + (hi - lo) // 2       # overflow-safe in fixed-width languages
        if a[m] == t: return m
        if a[m] < t: lo = m + 1
        else:        hi = m - 1
    return -1

Template B — boundaries, exclusive upper bound

This is the one to default to, because it answers more questions and has no lo <= hi off-by-one.

def lower_bound(a, t):                # first index with a[i] >= t   (== bisect_left)
    lo, hi = 0, len(a)                # EXCLUSIVE
    while lo < hi:                    # note <
        m = (lo + hi) // 2
        if a[m] < t: lo = m + 1
        else:        hi = m
    return lo

def upper_bound(a, t):                # first index with a[i] > t    (== bisect_right)
    lo, hi = 0, len(a)
    while lo < hi:
        m = (lo + hi) // 2
        if a[m] <= t: lo = m + 1
        else:         hi = m
    return lo

The only difference between them is < versus <=. From those two you get everything:

a = [1, 3, 3, 5, 5, 5, 9]
lower_bound(5)                  = 3     first occurrence
upper_bound(5)                  = 6     one past the last occurrence
upper_bound(5) - lower_bound(5) = 3     count of 5s
lower_bound(t)                          insertion point that keeps the array sorted
lower_bound(t)                          index of the smallest element >= t  (ceil)
lower_bound(t) - 1                      index of the largest element  < t  (floor)
lower_bound(t)                          rank: how many elements are strictly less than t
lower_bound(t) == len(a)                t is larger than everything

Verified against bisect.bisect_left and bisect.bisect_right for every case.

Template C — first true of a monotone predicate

The generalization, and the one that unlocks section 11.

def binary_search_predicate(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) True. Requires pred to be monotone:
       F F F F T T T T  — once true, always true."""
    while lo < hi:
        m = lo + (hi - lo) // 2
        if pred(m): hi = m
        else:       lo = m + 1
    return lo

The four ways people get it wrong

1. The loop does not shrink. hi = m with while lo <= hi loops forever when lo == hi. Pair inclusive bounds with m ± 1 updates, and exclusive bounds with hi = m.
2. Overflow. (lo + hi) / 2 overflows in Java/C/C++/Go for large indices — the famous bug that sat in java.util.Arrays.binarySearch for nine years. lo + (hi - lo) / 2 is safe. In Python and JavaScript there is no overflow (arbitrary-precision ints; doubles up to 2^53), so this is a “know why the idiom exists” answer rather than a real hazard.
3. Searching unsorted data. Binary search’s precondition is monotonicity. If you sort first, you paid O(n log n) and a linear scan was free.
4. Forgetting the empty and single-element cases. Template B handles both without special-casing, which is the main reason to prefer it.

11. Binary searching the answer

This is the pattern that separates people who “know binary search” from people who can use it. When the question is “find the minimum X such that something is achievable”, and achievability is monotone in X, you binary search over the answer space and use a linear feasibility check as the predicate.

The recognition signals: “minimize the maximum”, “maximize the minimum”, “smallest capacity/speed/size such that…”, and any answer range you can bound.

def min_capacity_to_ship(weights, days):
    """Ship packages in order within `days` days; minimize the daily capacity."""
    def feasible(cap):                                  # monotone: bigger cap is never worse
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap: d += 1; cur = 0
            cur += w
        return d <= days
    lo, hi = max(weights), sum(weights)                 # bound the answer space
    return binary_search_predicate(lo, hi, feasible)    # O(n log(sum))

Verified: min_capacity_to_ship([1..10], 5) == 15 and min_capacity_to_ship([3,2,2,4,1,4], 3) == 6.

The same shape solves a long list of problems:

Two related “binary search on a value, not an index” techniques worth naming:

def sqrt_int(n):
    """Integer square root. Binary search on the answer with a monotone predicate m*m <= n."""
    lo, hi, ans = 0, n, 0
    while lo <= hi:
        m = (lo + hi) // 2
        if m * m <= n: ans = m; lo = m + 1
        else: hi = m - 1
    return ans

Verified for 0, 1, 8, 9, and 1e12. Also: exponential (galloping) search for an unbounded or infinite sorted sequence — double the upper bound until the predicate flips, then binary search the last interval. O(log i) where i is the answer’s position, and it is how you binary search a stream or an API with an unknown length.

def exponential_search(pred):
    hi = 1
    while not pred(hi): hi *= 2
    return binary_search_predicate(hi // 2, hi, pred)

12. The hard binary searches

Rotated sorted array

def search_rotated(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        m = (lo + hi) // 2
        if a[m] == t: return m
        if a[lo] <= a[m]:                       # the LEFT half is sorted
            if a[lo] <= t < a[m]: hi = m - 1    # target is inside it
            else: lo = m + 1
        else:                                   # the RIGHT half is sorted
            if a[m] < t <= a[hi]: lo = m + 1
            else: hi = m - 1
    return -1

def find_min_rotated(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        m = (lo + hi) // 2
        if a[m] > a[hi]: lo = m + 1              # the minimum is strictly right of m
        else: hi = m
    return a[lo]

The invariant that makes it work: at least one of the two halves is always fully sorted, and you can tell which by comparing a[lo] to a[m]. Then it is an ordinary containment test. With duplicates the a[lo] == a[m] case is ambiguous and the worst case degrades to O(n) — say that, because it is the follow-up.

Peak in a bitonic array

def peak_index(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        m = (lo + hi) // 2
        if a[m] < a[m + 1]: lo = m + 1           # we are on the rising side
        else: hi = m
    return lo

Binary search does not need global sortedness — it needs a local rule that eliminates half the space. Comparing a neighbour is enough. That reframing is the point of the question.

Median of two sorted arrays in O(log min(m, n))

The hardest common binary-search question. Search for the partition point rather than the value.

def median_two_sorted(a, b):
    if len(a) > len(b): a, b = b, a               # always binary search the SHORTER array
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2                        # take i from a...
        j = half - i                              # ...and the rest from b
        aL = a[i-1] if i > 0 else float('-inf'); aR = a[i] if i < m else float('inf')
        bL = b[j-1] if j > 0 else float('-inf'); bR = b[j] if j < n else float('inf')
        if aL <= bR and bL <= aR:                 # valid partition found
            if (m + n) % 2: return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        if aL > bR: hi = i - 1                    # took too many from a
        else:       lo = i + 1
    raise ValueError('inputs not sorted')

Verified against brute force on 200 random pairs of arrays. The two ideas: the +/-infinity sentinels remove every boundary special case, and binary searching the shorter array is what makes the bound log min(m, n) rather than log(m+n).

13. Test run

  ok  12 sorts agree with sorted() on 8 input shapes (empty, single, sorted, reversed, random, all-equal, dupes)
  ok  merge sort and Python's sorted() are both stable (equal keys keep input order)
  ok  quickselect: kth smallest matches sorted()[k], expected O(n)

  Timsort adaptivity, list.sort() on 2,000,000 floats (CPython 3.11.15):
    input                          seconds   vs random
    random                          0.6453        1.0x
    already sorted                  0.0697        9.3x
    reversed                        0.0640       10.1x
    nearly sorted (0.1% swaps)      0.0852        7.6x

  ok  6 sorts agree with Array.prototype.sort on 8 input shapes            [TypeScript]
  ok  default Array.sort() is lexicographic: [10,9,1].sort() === [1,10,9]
  ok  V8 sort is stable (guaranteed by ES2019, implemented as TimSort)
  ok  hand-written merge sort is stable because the merge uses <= not <
  ok  quickselect: kth smallest matches sorted[k]

  ok  binary search: exact, lower_bound, upper_bound — all agree with bisect
  ok  rotated array: search and find-minimum in O(log n)
  ok  peak finding on a bitonic array
  ok  integer sqrt by binary search on the answer
  ok  binary search on the ANSWER (min ship capacity) using a monotone predicate
  ok  median of two sorted arrays in O(log min(m,n)) — 200 random cases vs brute force

14. Interview questions

Q: Which sort would you use and why?

A: In real code, the built-in — it is TimSort in Python and JavaScript, which is stable, O(n log n) guaranteed, and adaptive (measured 9x faster on sorted input). If I had to write one: merge sort when I need stability or a linked list, quicksort with a randomized pivot when I need in-place and average speed, heapsort when I need a worst-case guarantee with O(1) space.

Q: Why is quicksort usually faster than merge sort despite the worse worst case?

A: It is in place, so its two sequential scans have far better cache locality and it allocates nothing. Merge sort’s O(n) buffer plus the copy traffic costs more than the extra comparisons quicksort sometimes does.

Q: How do you make quicksort’s worst case go away?

A: Randomize the pivot (removes adversarial input), use median-of-three (helps on sorted input), recurse into the smaller side (bounds the stack at O(log n)), and add a depth counter that switches to heapsort — that last one is introsort, and it gives a hard O(n log n) guarantee.

Q: What makes a sort stable, and when do you care?

A: Equal elements keep their input order. It matters whenever you sort by more than one key, whenever the sort feeds a downstream stable process, and whenever the “equal” elements are distinguishable to the user (rows in a table).

Q: Can you sort in O(n)?

A: Not with comparisons — the decision-tree bound is Omega(n log n). With bounded integer keys, counting sort is O(n + k); with fixed-width keys, radix is O(d(n + b)).

Q: Sort a linked list in O(n log n) and O(1) extra space.

A: Bottom-up merge sort: relink nodes instead of copying, iterating over run widths 1, 2, 4, … Top-down needs O(log n) stack; quicksort on a list has terrible constants.

Q: Sort a 100 GB file with 1 GB of RAM.

A: External merge sort: read chunks that fit, sort each in memory, write them out as runs, then k-way merge the runs with a min-heap (heapq.merge). I/O-bound, so tune the chunk size and the merge fan-in to the available memory and the sequential read throughput.

Q: Why does heapify cost O(n) rather than O(n log n)?

A: Sift down from the last internal node up. Nodes at height h cost O(h) and there are at most n/2^(h+1) of them; the sum telescopes to 2n. Most nodes are near the leaves.

Q: Why does [10, 9, 1].sort() give [1, 10, 9] in JavaScript?

A: With no comparator, sort converts each element to a string and compares UTF-16 code units. '10' < '9'. Always pass (a, b) => a - b for numbers.

Q: Is Array.prototype.sort stable?

A: Yes, guaranteed since ES2019, and V8 implements it as TimSort. TypedArray.prototype.sort is a separate code path with numeric ordering.

Q: What is the difference between key= and cmp= in Python, and why did cmp go away?

A: key is called once per element (n calls) and produces a sortable surrogate; a comparator is called O(n log n) times. cmp was removed in Python 3 because key is faster and composes better; functools.cmp_to_key remains for genuinely comparator-shaped orderings like “largest concatenated number”.

Q: How do you find the kth largest element in an array?

A: Quickselect for O(n) expected with mutation allowed; a size-k min-heap for O(n log k) and streaming input; heapq.nlargest(k, xs)[-1] in Python. Sorting is O(n log n) and only worth it if you need the order anyway.

Q: How do you find the median of a stream?

A: Two heaps — a max-heap of the lower half and a min-heap of the upper half, rebalanced to differ by at most one. O(log n) insert, O(1) query. See Python data structures §16.

Q: Binary search: lo <= hi or lo < hi?

A: lo <= hi with inclusive bounds and m ± 1 updates for exact match; lo < hi with an exclusive upper bound and hi = m for boundary searches. Mixing the two is what produces infinite loops. Default to the second template.

Q: Why mid = lo + (hi - lo) / 2?

A: (lo + hi) / 2 overflows for large indices in fixed-width languages — the real bug in java.util.Arrays.binarySearch for nine years. Python’s ints and JavaScript’s doubles do not overflow at these magnitudes, but the idiom is still worth writing because it communicates that you know.

Q: How would you binary search when the array is rotated?

A: At every step one half is fully sorted; compare a[lo] to a[mid] to find out which, then test containment in that half. With duplicates the ambiguous case degrades the worst case to O(n).

Q: Give me a binary search that is not over an array.

A: “Minimize the maximum load” problems: binary search the answer value and use a linear greedy feasibility check as the monotone predicate. Also integer square root, and exponential search over an unbounded sequence.

Q: What is the precondition for binary search?

A: Monotonicity of the predicate you are testing — not sortedness of the data per se. The peak-finding example uses a local comparison with a neighbour and no global order at all.

Q: How do you count inversions in an array?

A: A merge sort that adds len(left) - i to the count each time it takes an element from the right half. O(n log n). Or a Fenwick tree over compressed ranks, sweeping right to left.

Q: Given intervals, find the minimum number of meeting rooms.

A: Sort by start; keep a min-heap of end times; pop while the earliest end is <= the current start; the heap’s maximum size is the answer. O(n log n).

Q: Interval scheduling — which greedy is correct?

A: Sort by earliest end time and take greedily. Sorting by start time or by shortest duration both produce counterexamples. Say the exchange argument: any optimal solution can be modified to include the earliest-ending interval without getting worse.

Q: When is bucket sort O(n^2)?

A: When the input is skewed and everything lands in one bucket, so the inner sort dominates. It needs a roughly uniform key distribution, which is a strong assumption.

Q: What does “adaptive” buy you in practice?

A: Measured here: 7.6x on data that is 99.9% sorted, and 9.3x on fully sorted data. Real datasets are usually partly ordered (appended logs, re-sorted tables, merged streams), so this is not a synthetic win.

Next: Algorithm patterns for the two-pointer, sliding-window and monotonic-stack families that reuse the machinery here.

Verify it yourself

sorts/bs.py

import bisect, random
out=[]
def ok(m): out.append("  ok  "+m)

def bsearch(a, t):
    lo, hi = 0, len(a)-1                      # INCLUSIVE bounds
    while lo <= hi:
        m = lo + (hi-lo)//2
        if a[m]==t: return m
        if a[m] < t: lo = m+1
        else: hi = m-1
    return -1

def lower_bound(a, t):                        # first index with a[i] >= t
    lo, hi = 0, len(a)                        # EXCLUSIVE hi
    while lo < hi:
        m = (lo+hi)//2
        if a[m] < t: lo = m+1
        else: hi = m
    return lo

def upper_bound(a, t):                        # first index with a[i] > t
    lo, hi = 0, len(a)
    while lo < hi:
        m = (lo+hi)//2
        if a[m] <= t: lo = m+1
        else: hi = m
    return lo

def binary_search_predicate(lo, hi, pred):    # first x in [lo, hi] with pred(x) True (monotone)
    while lo < hi:
        m = lo + (hi-lo)//2
        if pred(m): hi = m
        else: lo = m+1
    return lo

def search_rotated(a, t):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        m = (lo+hi)//2
        if a[m]==t: return m
        if a[lo] <= a[m]:                     # left half is sorted
            if a[lo] <= t < a[m]: hi = m-1
            else: lo = m+1
        else:                                 # right half is sorted
            if a[m] < t <= a[hi]: lo = m+1
            else: hi = m-1
    return -1

def find_min_rotated(a):
    lo, hi = 0, len(a)-1
    while lo < hi:
        m = (lo+hi)//2
        if a[m] > a[hi]: lo = m+1
        else: hi = m
    return a[lo]

def peak_index(a):
    lo, hi = 0, len(a)-1
    while lo < hi:
        m = (lo+hi)//2
        if a[m] < a[m+1]: lo = m+1
        else: hi = m
    return lo

def sqrt_int(n):
    lo, hi, ans = 0, n, 0
    while lo <= hi:
        m = (lo+hi)//2
        if m*m <= n: ans = m; lo = m+1
        else: hi = m-1
    return ans

def min_capacity_to_ship(weights, days):
    def ok_cap(cap):
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap: d += 1; cur = 0
            cur += w
        return d <= days
    lo, hi = max(weights), sum(weights)
    return binary_search_predicate(lo, hi, ok_cap)

def median_two_sorted(a, b):
    if len(a) > len(b): a, b = b, a
    m, n = len(a), len(b); half = (m+n+1)//2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo+hi)//2; j = half - i
        aL = a[i-1] if i > 0 else float('-inf'); aR = a[i] if i < m else float('inf')
        bL = b[j-1] if j > 0 else float('-inf'); bR = b[j] if j < n else float('inf')
        if aL <= bR and bL <= aR:
            if (m+n) % 2: return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        if aL > bR: hi = i-1
        else: lo = i+1
    raise ValueError

a = [1,3,3,5,5,5,9]
assert bsearch(a,5) in (3,4,5) and bsearch(a,4) == -1
assert lower_bound(a,5)==3 and upper_bound(a,5)==6 and upper_bound(a,5)-lower_bound(a,5)==3
assert lower_bound(a,5)==bisect.bisect_left(a,5) and upper_bound(a,5)==bisect.bisect_right(a,5)
assert lower_bound(a,0)==0 and lower_bound(a,10)==len(a)
ok("binary search: exact, lower_bound, upper_bound — all agree with bisect")
rot=[4,5,6,7,0,1,2]
assert search_rotated(rot,0)==4 and search_rotated(rot,3)==-1 and find_min_rotated(rot)==0
assert find_min_rotated([1,2,3])==1
ok("rotated array: search and find-minimum in O(log n)")
assert peak_index([1,3,5,4,2])==2 and peak_index([1,2,3])==2
ok("peak finding on a bitonic array")
assert sqrt_int(0)==0 and sqrt_int(1)==1 and sqrt_int(8)==2 and sqrt_int(9)==3 and sqrt_int(10**12)==10**6
ok("integer sqrt by binary search on the answer")
assert min_capacity_to_ship([1,2,3,4,5,6,7,8,9,10],5)==15
assert min_capacity_to_ship([3,2,2,4,1,4],3)==6
ok("binary search on the ANSWER (min ship capacity) using a monotone predicate")
assert median_two_sorted([1,3],[2])==2.0 and median_two_sorted([1,2],[3,4])==2.5
for _ in range(200):
    x=sorted(random.randint(0,50) for _ in range(random.randint(1,8)))
    y=sorted(random.randint(0,50) for _ in range(random.randint(1,8)))
    merged=sorted(x+y); k=len(merged)
    expect = merged[k//2] if k%2 else (merged[k//2-1]+merged[k//2])/2
    assert median_two_sorted(x,y)==expect
ok("median of two sorted arrays in O(log min(m,n)) — 200 random cases vs brute force")
# overflow note
lo, hi = 2**62, 2**62+10
assert lo + (hi-lo)//2 == (lo+hi)//2      # Python has arbitrary precision, so both are fine
ok("mid = lo + (hi-lo)//2 avoids overflow in fixed-width languages; Python ints cannot overflow")
print("\n".join(out)); print("\nALL BINARY SEARCH ASSERTIONS PASSED")

sorts/s.py

import random, sys, time
from typing import Callable
out=[]
def ok(m): out.append("  ok  "+m)

def bubble(a):
    a=a[:]; n=len(a)
    for i in range(n):
        swapped=False
        for j in range(n-1-i):
            if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j]; swapped=True
        if not swapped: break          # early exit -> O(n) on sorted input
    return a
def selection(a):
    a=a[:]; n=len(a)
    for i in range(n):
        m=i
        for j in range(i+1,n):
            if a[j]<a[m]: m=j
        a[i],a[m]=a[m],a[i]
    return a
def insertion(a):
    a=a[:]
    for i in range(1,len(a)):
        cur=a[i]; j=i-1
        while j>=0 and a[j]>cur: a[j+1]=a[j]; j-=1
        a[j+1]=cur
    return a
def shell(a):
    a=a[:]; n=len(a); gap=1
    while gap < n//3: gap = 3*gap+1        # Knuth sequence
    while gap:
        for i in range(gap,n):
            cur=a[i]; j=i
            while j>=gap and a[j-gap]>cur: a[j]=a[j-gap]; j-=gap
            a[j]=cur
        gap//=3
    return a
def merge_sort(a):
    if len(a)<=1: return a[:]
    m=len(a)//2
    return _merge(merge_sort(a[:m]), merge_sort(a[m:]))
def _merge(l,r):
    out=[]; i=j=0
    while i<len(l) and j<len(r):
        if l[i]<=r[j]: out.append(l[i]); i+=1     # <= preserves stability
        else: out.append(r[j]); j+=1
    out.extend(l[i:]); out.extend(r[j:]); return out
def merge_sort_bu(a):
    a=a[:]; n=len(a); width=1
    while width<n:
        for i in range(0,n,2*width):
            a[i:i+2*width]=_merge(a[i:i+width], a[i+width:i+2*width])
        width*=2
    return a
def quicksort(a):
    a=a[:]
    def part(lo,hi):
        p=random.randint(lo,hi); a[p],a[hi]=a[hi],a[p]   # randomized pivot
        pivot=a[hi]; i=lo
        for j in range(lo,hi):
            if a[j]<pivot: a[i],a[j]=a[j],a[i]; i+=1
        a[i],a[hi]=a[hi],a[i]; return i
    def go(lo,hi):
        while lo<hi:
            p=part(lo,hi)
            if p-lo < hi-p: go(lo,p-1); lo=p+1       # recurse on the SMALLER side -> O(log n) stack
            else: go(p+1,hi); hi=p-1
    go(0,len(a)-1); return a
def quicksort_3way(a):
    a=a[:]
    def go(lo,hi):
        if lo>=hi: return
        pivot=a[random.randint(lo,hi)]
        lt,i,gt=lo,lo,hi
        while i<=gt:
            if a[i]<pivot: a[lt],a[i]=a[i],a[lt]; lt+=1; i+=1
            elif a[i]>pivot: a[i],a[gt]=a[gt],a[i]; gt-=1
            else: i+=1
        go(lo,lt-1); go(gt+1,hi)
    go(0,len(a)-1); return a
def heapsort(a):
    a=a[:]; n=len(a)
    def sift(i,size):
        while True:
            big,l,r=i,2*i+1,2*i+2
            if l<size and a[l]>a[big]: big=l
            if r<size and a[r]>a[big]: big=r
            if big==i: return
            a[i],a[big]=a[big],a[i]; i=big
    for i in range(n//2-1,-1,-1): sift(i,n)
    for end in range(n-1,0,-1):
        a[0],a[end]=a[end],a[0]; sift(0,end)
    return a
def counting_sort(a, lo=None, hi=None):
    if not a: return []
    lo = min(a) if lo is None else lo
    hi = max(a) if hi is None else hi
    cnt=[0]*(hi-lo+1)
    for x in a: cnt[x-lo]+=1
    for i in range(1,len(cnt)): cnt[i]+=cnt[i-1]   # prefix sums -> stable placement
    out=[0]*len(a)
    for x in reversed(a):                           # reversed keeps it stable
        cnt[x-lo]-=1; out[cnt[x-lo]]=x
    return out
def radix_sort(a):
    if not a: return []
    neg=[-x for x in a if x<0]; pos=[x for x in a if x>=0]
    def lsd(xs):
        if not xs: return []
        maxv=max(xs); exp=1
        while maxv//exp>0:
            buckets=[[] for _ in range(10)]
            for x in xs: buckets[(x//exp)%10].append(x)
            xs=[x for b in buckets for x in b]
            exp*=10
        return xs
    return [-x for x in reversed(lsd(neg))] + lsd(pos)
def bucket_sort(a):
    if not a: return []
    n=len(a); lo,hi=min(a),max(a)
    if lo==hi: return a[:]
    buckets=[[] for _ in range(n)]
    for x in a:
        idx=int((x-lo)/(hi-lo)*(n-1)); buckets[idx].append(x)
    return [x for b in buckets for x in insertion(b)]
def quickselect(a,k):
    a=a[:]; lo,hi=0,len(a)-1
    while True:
        if lo==hi: return a[lo]
        p=random.randint(lo,hi); a[p],a[hi]=a[hi],a[p]
        pivot=a[hi]; i=lo
        for j in range(lo,hi):
            if a[j]<pivot: a[i],a[j]=a[j],a[i]; i+=1
        a[i],a[hi]=a[hi],a[i]
        if k==i: return a[i]
        if k<i: hi=i-1
        else: lo=i+1

algos: dict[str, Callable] = dict(bubble=bubble, selection=selection, insertion=insertion,
    shell=shell, merge=merge_sort, merge_bu=merge_sort_bu, quick=quicksort, quick3=quicksort_3way,
    heap=heapsort, counting=counting_sort, radix=radix_sort, bucket=bucket_sort)
cases = [[], [1], [2,1], list(range(20)), list(range(20))[::-1],
         [random.randint(-50,50) for _ in range(200)], [5]*30, [3,1,3,1,3]]
for name,fn in algos.items():
    for c in cases:
        assert fn(c)==sorted(c), (name, c[:10], fn(c)[:10])
ok(f"12 sorts agree with sorted() on 8 input shapes (empty, single, sorted, reversed, random, all-equal, dupes)")

# stability check
recs=[(1,'a'),(0,'b'),(1,'c'),(0,'d'),(1,'e')]
def stable_merge(a, key=lambda x:x[0]):
    if len(a)<=1: return a[:]
    m=len(a)//2; l,r=stable_merge(a[:m],key),stable_merge(a[m:],key); out=[];i=j=0
    while i<len(l) and j<len(r):
        if key(l[i])<=key(r[j]): out.append(l[i]); i+=1
        else: out.append(r[j]); j+=1
    out.extend(l[i:]); out.extend(r[j:]); return out
assert stable_merge(recs)==[(0,'b'),(0,'d'),(1,'a'),(1,'c'),(1,'e')]
assert sorted(recs, key=lambda x:x[0])==[(0,'b'),(0,'d'),(1,'a'),(1,'c'),(1,'e')]
ok("merge sort and Python's sorted() are both stable (equal keys keep input order)")

# quickselect
data=[random.randint(0,1000) for _ in range(500)]
srt=sorted(data)
assert all(quickselect(data,k)==srt[k] for k in (0, 1, 249, 499))
ok("quickselect: kth smallest matches sorted()[k], expected O(n)")

# Timsort run detection: measured on sorted vs random
def t(label, arr):
    a=arr[:]; s=time.perf_counter(); a.sort(); return time.perf_counter()-s
N=2_000_000
rand=[random.random() for _ in range(N)]
srt2=sorted(rand)
rev=srt2[::-1]
nearly=srt2[:]; 
for _ in range(N//1000):
    i=random.randrange(N); j=random.randrange(N); nearly[i],nearly[j]=nearly[j],nearly[i]
rows=[("random", t("",rand)), ("already sorted", t("",srt2)), ("reversed", t("",rev)), ("nearly sorted (0.1% swaps)", t("",nearly))]
base=rows[0][1]
out.append("")
out.append(f"  Timsort adaptivity, list.sort() on {N:,} floats (CPython {sys.version.split()[0]}):")
out.append(f"    {'input':<28}{'seconds':>10}{'vs random':>12}")
for lbl,secs in rows:
    out.append(f"    {lbl:<28}{secs:>10.4f}{base/secs:>11.1f}x")
print("\n".join(out))
print(f"\nALL SORT ASSERTIONS PASSED")

sorts/s.ts

import assert from 'node:assert/strict';
const out: string[] = []; const ok = (m: string) => out.push('  ok  ' + m);
type Cmp<T> = (a: T, b: T) => number;
const num: Cmp<number> = (a, b) => a - b;

function insertionSort<T>(a: T[], cmp: Cmp<T> = num as Cmp<T>, lo = 0, hi = a.length - 1): T[] {
  for (let i = lo + 1; i <= hi; i++) {
    const cur = a[i]!; let j = i - 1;
    while (j >= lo && cmp(a[j]!, cur) > 0) { a[j + 1] = a[j]!; j--; }
    a[j + 1] = cur;
  }
  return a;
}
function mergeSort<T>(a: readonly T[], cmp: Cmp<T> = num as Cmp<T>): T[] {
  if (a.length <= 1) return [...a];
  const m = a.length >> 1;
  return merge(mergeSort(a.slice(0, m), cmp), mergeSort(a.slice(m), cmp), cmp);
}
function merge<T>(l: T[], r: T[], cmp: Cmp<T>): T[] {
  const out: T[] = []; let i = 0, j = 0;
  while (i < l.length && j < r.length) out.push(cmp(l[i]!, r[j]!) <= 0 ? l[i++]! : r[j++]!);
  while (i < l.length) out.push(l[i++]!);
  while (j < r.length) out.push(r[j++]!);
  return out;
}
function quickSort<T>(a: T[], cmp: Cmp<T> = num as Cmp<T>, lo = 0, hi = a.length - 1): T[] {
  while (lo < hi) {
    if (hi - lo < 16) { insertionSort(a, cmp, lo, hi); return a; }      // introsort-style cutoff
    const p = partition(a, cmp, lo, hi);
    if (p - lo < hi - p) { quickSort(a, cmp, lo, p - 1); lo = p + 1; }  // recurse on the smaller side
    else { quickSort(a, cmp, p + 1, hi); hi = p - 1; }
  }
  return a;
}
function partition<T>(a: T[], cmp: Cmp<T>, lo: number, hi: number): number {
  const mid = (lo + hi) >> 1;                                          // median-of-three
  const order = [lo, mid, hi].sort((x, y) => cmp(a[x]!, a[y]!));
  [a[order[1]!], a[hi]] = [a[hi]!, a[order[1]!]!];
  const pivot = a[hi]!; let i = lo;
  for (let j = lo; j < hi; j++) if (cmp(a[j]!, pivot) < 0) { [a[i], a[j]] = [a[j]!, a[i]!]; i++; }
  [a[i], a[hi]] = [a[hi]!, a[i]!];
  return i;
}
function heapSort<T>(a: T[], cmp: Cmp<T> = num as Cmp<T>): T[] {
  const n = a.length;
  const sift = (i: number, size: number) => {
    for (;;) {
      let big = i; const l = 2 * i + 1, r = 2 * i + 2;
      if (l < size && cmp(a[l]!, a[big]!) > 0) big = l;
      if (r < size && cmp(a[r]!, a[big]!) > 0) big = r;
      if (big === i) return;
      [a[i], a[big]] = [a[big]!, a[i]!]; i = big;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) sift(i, n);
  for (let end = n - 1; end > 0; end--) { [a[0], a[end]] = [a[end]!, a[0]!]; sift(0, end); }
  return a;
}
function countingSort(a: readonly number[]): number[] {
  if (!a.length) return [];
  const lo = Math.min(...a), hi = Math.max(...a);
  const cnt = new Int32Array(hi - lo + 1);
  for (const x of a) cnt[x - lo]!++;
  for (let i = 1; i < cnt.length; i++) cnt[i]! += cnt[i - 1]!;
  const out = new Array<number>(a.length);
  for (let i = a.length - 1; i >= 0; i--) { const x = a[i]!; out[--cnt[x - lo]!] = x; }
  return out;
}
function radixSort(a: readonly number[]): number[] {
  const neg = a.filter(x => x < 0).map(x => -x), pos = a.filter(x => x >= 0);
  const lsd = (xs: number[]): number[] => {
    if (!xs.length) return [];
    let cur = xs, exp = 1, max = Math.max(...xs);
    while (Math.floor(max / exp) > 0) {
      const buckets: number[][] = Array.from({ length: 10 }, () => []);
      for (const x of cur) buckets[Math.floor(x / exp) % 10]!.push(x);
      cur = buckets.flat(); exp *= 10;
    }
    return cur;
  };
  return [...lsd(neg).reverse().map(x => -x), ...lsd(pos)];
}
function quickselect<T>(a: T[], k: number, cmp: Cmp<T> = num as Cmp<T>): T {
  let lo = 0, hi = a.length - 1;
  for (;;) {
    if (lo === hi) return a[lo]!;
    const p = partition(a, cmp, lo, hi);
    if (k === p) return a[p]!;
    if (k < p) hi = p - 1; else lo = p + 1;
  }
}
const cases: number[][] = [[], [1], [2, 1], [...Array(20).keys()], [...Array(20).keys()].reverse(),
  Array.from({ length: 200 }, () => Math.floor(Math.random() * 101) - 50), new Array(30).fill(5), [3, 1, 3, 1, 3]];
const impls: Array<[string, (a: number[]) => number[]]> = [
  ['insertion', a => insertionSort([...a])], ['merge', a => mergeSort(a)],
  ['quick', a => quickSort([...a])], ['heap', a => heapSort([...a])],
  ['counting', a => countingSort(a)], ['radix', a => radixSort(a)]];
for (const [name, fn] of impls)
  for (const c of cases)
    assert.deepEqual(fn(c), [...c].sort(num), name);
ok('6 sorts agree with Array.prototype.sort on 8 input shapes');

// default comparator trap
assert.deepEqual([10, 9, 1].sort(), [1, 10, 9]);
assert.deepEqual([10, 9, 1].sort((a, b) => a - b), [1, 9, 10]);
ok('default Array.sort() is lexicographic: [10,9,1].sort() === [1,10,9]');

// stability of V8 TimSort
const recs = [[1, 'a'], [0, 'b'], [1, 'c'], [0, 'd'], [1, 'e']] as Array<[number, string]>;
assert.deepEqual([...recs].sort((x, y) => x[0] - y[0]).map(r => r[1]).join(''), 'bdace');
ok('V8 sort is stable (guaranteed by ES2019, implemented as TimSort)');

// merge sort stability
assert.deepEqual(mergeSort(recs, (x, y) => x[0] - y[0]).map(r => r[1]).join(''), 'bdace');
ok('hand-written merge sort is stable because the merge uses <= not <');

const data = Array.from({ length: 500 }, () => Math.floor(Math.random() * 1000));
const srt = [...data].sort(num);
for (const k of [0, 1, 249, 499]) assert.equal(quickselect([...data], k), srt[k]);
ok('quickselect: kth smallest matches sorted[k]');

console.log(out.join('\n'));
console.log('\nALL TS SORT ASSERTIONS PASSED');