13Module · Goodrich Ch. 12

Week 13 — Sorting & Selection

Merge-sort, quick-sort, sorting lower bound, bucket/radix-sort, and randomized selection.

Comparison-based and non-comparison sorting, plus expected linear-time selection of the k-th smallest element.

Theory

Merge-sort divides, recursively sorts, and merges in O(n log n) worst case with O(n) auxiliary space; it is stable.

Quick-sort partitions around a pivot; expected O(n log n) with random pivots, but O(n²) on pathological inputs.

Any comparison sort has an Ω(n log n) lower bound (decision-tree argument).

Bucket and radix sort beat the bound when keys fit a bounded range or have fixed digit width: O(n + r) and O(d·(n + r)).

Randomized quick-select finds the k-th smallest in expected O(n) using partition.

Key points

Mergesort is stable; quicksort and heapsort are not.
Python's Timsort (used by sorted/.sort()) is stable and adaptive, O(n log n).
Median-of-medians gives a deterministic O(n) selection algorithm.

Code examples

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:])
    out, i, j = [], 0, 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

Randomized quick-select

import random

def quick_select(a, k):
    if len(a) == 1:
        return a[0]
    pivot = random.choice(a)
    lows  = [x for x in a if x < pivot]
    highs = [x for x in a if x > pivot]
    pivots = [x for x in a if x == pivot]
    if k < len(lows):
        return quick_select(lows, k)
    if k < len(lows) + len(pivots):
        return pivot
    return quick_select(highs, k - len(lows) - len(pivots))