Searching and Sorting

1Merge sort: divide, sort, merge

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted runs into one. Every merge of two runs of total length m costs O(m) comparisons and writes, and the recursion tree has \Theta(\log n) levels, so the whole sort is O(n \log n) in every case. The price is an O(n) auxiliary buffer for the merge. Equal keys keep their relative order when the merge prefers the left run on ties — merge sort is stable.

Figure. Last merge of the worked example: left run [2, 5] with right run [1, 3, 4] yields [1, 2, 3, 4, 5].

How it works

1. SplitCut at mid until every piece has one element.
2. MergeWalk two sorted runs with two pointers; always take the smaller head (left on ties).
3. Cost\log n levels × O(n) work per level ⇒ O(n \log n); need an O(n) buffer.

Top-down merge sort

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Coding lab. Merge-sort [5, 2, 4, 1, 3] runs in the app, with checks on your output.

2Quick sort: partition around a pivot

Quick sort picks a pivot, partitions so every left element is \leq pivot and every right element is \geq pivot, then recurses on the two sides. Average time is O(n \log n) when partitions are reasonably balanced; the partition itself is in-place, and recursion uses O(\log n) stack on average. Unlike merge sort, the classic in-place form is not stable.

Figure. After partitioning [3, 1, 4, 2] with pivot 2: array is [1, 2, 4, 3]. Pivot sits at index 1.

Lomuto partition sketch

1. PivotChoose an element (here: last) and treat it as the split value.
2. ScanGrow a left region of values ≤ pivot; swap each such value into place.
3. Place pivotSwap the pivot into the boundary; recurse on left and right sides.

Quick sort with Lomuto partition

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

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

3Quick sort's O(n^2) trap

If every pivot is an extreme (smallest or largest remaining value), each partition peels off only one element and the recurrence becomes T(n) = T(n-1) + O(n). That sums to \Theta(n^2). Already-sorted input with a naive first/last pivot is the classic trigger. Randomizing the pivot (or median-of-three) makes that adversarial pattern vanishingly unlikely without changing the average O(n \log n) story.

Figure. A sorted input with a fixed end pivot yields n+(n-1)+\cdots partitions — randomise or median-of-three.

Why it squares

1. Bad pivotPartition sizes become 0 and n-1 every time.
2. Cost sumWork n + (n-1) + \cdots + 1 = n(n+1)/2.
3. MitigationShuffle, pick a random pivot, or use median-of-three before partitioning.

4Comparison sorts need \Omega(n \log n)

Any correct comparison-based sort must distinguish among n! possible input permutations. In the decision-tree model each comparison has two outcomes, so a tree of height h has at most 2^h leaves. Need 2^h \ge n!, hence h \ge \log_2(n!). Stirling's approximation gives \log_2(n!) = \Omega(n \log n), so every comparison sort has worst-case \Omega(n \log n) comparisons. Merge, heap and (balanced) quick sort all meet this bound up to constants; counting and radix escape it by not comparing keys.

Figure. Any comparison sort needs \Omega(n\log n) in the worst case; linear sorts cheat with integer structure.

Decision-tree argument

1. LeavesNeed at least one leaf per permutation ⇒ \ge n! leaves.
2. Binary treeHeight h ⇒ \le 2^h leaves ⇒ h \ge \log_2(n!).
3. Stirling\log_2(n!) = \Omega(n \log n) — the information-theoretic floor.

5Heap sort: O(n \log n) in-place

Heap sort builds a max-heap in O(n) time, then repeatedly extracts the maximum into the end of the array. Each extract is O(\log n), so n extracts cost O(n \log n). Extra memory beyond the input array is O(1) (ignoring the call stack of an in-place sift). The sort is not stable: sifting moves equal keys past each other. Choose it when you need worst-case O(n \log n) without merge sort's linear buffer and can tolerate instability.

Figure. Heap sort keeps worst-case O(n \log n) with constant extra memory. Merge needs a linear buffer; quick is leaner but not worst-case safe. Heap sort is not stable.

Two phases

1. Buildheapify the array — O(n), not O(n \log n).
2. ExtractSwap root with the last unsorted slot; sift-down; shrink the heap.
3. Trade-offWorst-case O(n \log n), O(1) extra space, not stable.

6Counting sort for bounded integer keys

When keys are integers in a known range \{0, 1, \ldots, k-1\}, counting sort tallies how many times each key appears, then writes the output from the tallies (or from prefix sums for a stable variant). Time and space are O(n + k). If k = O(n), that is linear — beating the comparison lower bound because keys are used as indices, not compared. Unusable when k is huge (e.g. arbitrary 64-bit keys with no digit structure).

Figure. Input [2, 0, 2, 1, 0] tallies to count[0]=2, count[1]=1, count[2]=2 before emit.

Tally then emit

1. CountAllocate size-k array; increment count[key] for each input.
2. EmitWalk values 0..k-1; append each value count[v] times (stable forms use prefix sums and a reverse pass).
3. WhenOnly when k is modest relative to n — otherwise memory and the O(k) term dominate.

Counting sort (simple emit)

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

7Radix sort: digit-by-digit linear passes

Radix sort sorts integers (or fixed-length strings) one digit at a time. Least-significant-digit (LSD) radix runs a stable counting sort on digit 0, then digit 1, and so on through d digits in base b. Each pass is O(n + b); d passes give O(d(n + b)). When d is constant (or O(1) relative to word size) and b is modest, total time is linear in n — again outside the comparison model.

Each digit pass reuses the tally strip from Counting sort for bounded integer keys — stable counts on the current digit, LSD to MSD, until every place is ordered.

LSD outline

1. Stable passCounting-sort on the current digit; stability preserves earlier digit order.
2. Next digitMove to the next more-significant digit; repeat.
3. Costd passes ⇒ O(d(n+b)). Pick base b to balance pass count vs bucket work.

8Stability and choosing a sort

A sort is stable when equal keys keep their input order. That matters when you sort by a secondary key first and a primary key second — stability on the second pass preserves the secondary order among ties. Merge sort and properly implemented counting/radix are stable; typical in-place quick sort and heap sort are not. Pick merge for guaranteed O(n \log n) plus stability; quick for fast in-place average case when stability is irrelevant; counting/radix when keys are short integers; heap when you need worst-case O(n \log n) with O(1) extra space.

Figure. Stability keeps equal keys in their original relative order — required when you sort by a second key later.

Decision cues

1. Stable + guaranteedMerge sort (also natural on linked lists).
2. In-place average-fastQuick sort — randomize the pivot; drop stability.
3. Small integer rangeCounting or radix for linear O(n+k) / O(d(n+b)).