Sorting algorithms

What Python actually does, and the classics underneath. You almost never implement a sort — but you are constantly expected to reason about one.

Why this matters

In a real interview you call sorted(). But you are constantly expected to reason about sorting: "what's the complexity if I sort first?", "is this stable?", "can I do better than O(n log n) given the constraints?". To answer those you need a clear mental model of (a) what Python's built-in sort gives you, and (b) the classic algorithms and their trade-offs, so you can recognize when a special-case sort (counting/radix) or a partial sort (quickselect) wins.

Part 0 — what Python actually uses: Timsort

list.sort() and sorted() both use Timsort (Tim Peters, 2002). Facts an interviewer expects:

• Stable: equal elements keep their original relative order. This lets you sort by multiple keys in passes (sort by secondary key first, then by primary) — the stable sort preserves the earlier ordering within ties.
• O(n log n) worst case, O(n) on already-sorted or reverse-sorted input (it's adaptive — it finds existing sorted "runs" and merges them).
• A hybrid of merge sort (the run-merging skeleton) and insertion sort (to build/extend small runs, where insertion is fastest).
• In-place-ish: O(n) auxiliary space for the merge buffers.

The API you must be fluent in:

sorted(iterable, key=fn, reverse=bool)  # new list, original untouched
list.sort(key=fn, reverse=bool)         # sorts in place, returns None

# key=fn: sort by fn(x) instead of x. Computed ONCE per element
#         ("decorate-sort-undecorate"), so it's cheap even if fn is not.
# reverse=True: descending. STILL STABLE — ties keep original order
#         (Python reverses the comparison, not the final list).

Multi-key: sort by tuple keys. key=lambda p: (p.age, p.name) sorts by age then name. Or exploit stability: do the least-significant key first in its own pass.

people = [("Bob", 30), ("Ann", 25), ("Cay", 30), ("Dan", 25)]
# Sort by age ascending; within equal ages, ORIGINAL order is preserved.
by_age = sorted(people, key=lambda p: p[1])
# → [("Ann", 25), ("Dan", 25), ("Bob", 30), ("Cay", 30)]
# reverse=True is still stable: equal ages keep Bob-before-Cay.
by_age_desc = sorted(people, key=lambda p: p[1], reverse=True)
# → [("Bob", 30), ("Cay", 30), ("Ann", 25), ("Dan", 25)]
# Multi-key via tuple: age asc, then name asc.
multi = sorted(people, key=lambda p: (p[1], p[0]))

The comparison table

yes* = in-place in its classic array form; recursion uses O(log n) stack. k = key range; d = #digits; b = numeric base.

Part 1 — bubble sort (teaching baseline only)

Repeatedly walk the list swapping adjacent out-of-order pairs. After pass k the k largest elements have "bubbled" to the end. It makes "adjacent swaps → O(n²)" viscerally clear, and the early-exit flag is a nice adaptive teaching point. Never use it in practice.

def bubble_sort(a: List[int]) -> List[int]:
    a = a[:]  # copy so we don't mutate the caller's list
    n = len(a)
    for i in range(n):
        swapped = False
        # Last i elements are already in place → shrink the inner range.
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:  # a full clean pass → already sorted → stop (O(n) best)
            break
    return a

Part 2 — insertion sort (genuinely good for small / nearly-sorted)

Grow a sorted prefix. Take the next element and slide it left past all larger elements into position — exactly how you sort a hand of cards. Best O(n) (already sorted), avg/worst O(n²), O(1) space, stable. Use it when n is tiny (<~16) or the data is nearly sorted (few inversions) — this is exactly why Timsort uses it to build its small runs.

def insertion_sort(a: List[int]) -> List[int]:
    a = a[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # Slide elements greater than key one slot right to open a gap.
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key  # drop key into the opened gap
    return a

Part 3 — merge sort (canonical stable O(n log n) divide & conquer)

Split the list in half, sort each half recursively, then merge the two sorted halves in linear time. The recursion tree has depth log n and each level does O(n) merging work → O(n log n) always (it splits evenly). Needs O(n) extra space. Reach for it when you need guaranteed O(n log n) and stability; sorting linked lists (merge needs only sequential access); or external sorting of huge files.

def merge(left: List[int], right: List[int]) -> List[int]:
    """Merge two already-sorted lists into one. O(len(left)+len(right))."""
    merged: List[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        # '<=' (not '<') is what makes the merge STABLE: equal → take left first.
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # One side is exhausted; append the remainder of the other.
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def merge_sort(a: List[int]) -> List[int]:
    if len(a) <= 1:  # base case: 0 or 1 element is already sorted
        return a[:]
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

Part 4 — quicksort (in-place partitioning; fast in practice)

Pick a pivot, partition the array so everything ≤ pivot is on its left and everything > pivot on its right, then recurse on each side. No merge step. Average O(n log n) on balanced splits; worst O(n²) when partitions are maximally unbalanced (e.g. already-sorted input with a naive first/last pivot). Not stable. We use the middle element with a Hoare partition (two pointers converging from both ends).

def quicksort(a: List[int]) -> List[int]:
    a = a[:]
    _quicksort(a, 0, len(a) - 1)
    return a


def _quicksort(a: List[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return
    # Pivot = middle element (avoids the O(n²) trap on already-sorted inputs
    # that a fixed first/last pivot would hit).
    pivot = a[(lo + hi) // 2]
    i, j = lo, hi
    # HOARE partition: two pointers scan inward and swap inversions around the
    # pivot VALUE (not Lomuto, which keeps a single index scanning one way).
    while i <= j:
        while a[i] < pivot:
            i += 1
        while a[j] > pivot:
            j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
    # Now [lo..j] <= pivot and [i..hi] >= pivot; recurse each side.
    _quicksort(a, lo, j)
    _quicksort(a, i, hi)

Part 5 — heap sort (selection sort, but "find the min" is O(log n))

A binary heap lets you extract the minimum in O(log n). Heapify all n elements (O(n) bottom-up), then pop them all → sorted output. The n pops cost n × O(log n) → O(n log n) total. (Building by n separate pushes would also be O(n log n); heapify is O(n).) Use it when you need O(n log n) worst-case with O(1) extra space (no merge buffer), or you only need the top-k.

def heap_sort(a: List[int]) -> List[int]:
    import heapq  # local import: this is the only function that needs it
    h = a[:]
    heapq.heapify(h)  # O(n) bottom-up heap construction
    return [heapq.heappop(h) for _ in range(len(h))]  # n × O(log n) pops

Part 6 — counting sort (non-comparison; O(n + k) when keys are small ints)

Don't compare at all. If keys are integers in [0, k], count how many of each value occur, then emit values in order using the counts. The values are used directly as array indices — that's how it dodges the n log n lower bound. This implementation is stable (we walk inputs in order when placing).

def counting_sort(a: List[int]) -> List[int]:
    if not a:
        return []
    lo, hi = min(a), max(a)              # support negatives by offsetting by lo
    counts = [0] * (hi - lo + 1)         # one bucket per possible value
    for x in a:
        counts[x - lo] += 1              # tally occurrences
    out: List[int] = []
    for value_offset, c in enumerate(counts):
        out.extend([value_offset + lo] * c)  # emit each value `count` times, in order
    return out

Part 7 — radix sort (LSD: sort by each digit using a stable counting sort)

Counting sort fails when k is large, but we can sort by one digit at a time. Process digits least-significant first, using a stable sort each pass. After processing all d digits, the array is fully sorted — stability is what makes earlier, less-significant orderings survive within later ties. O(d · (n + base)); for fixed-width integers d is constant → effectively O(n).

def radix_sort(a: List[int]) -> List[int]:
    if not a:
        return []
    assert min(a) >= 0, "this teaching radix sort handles non-negative ints only"
    out = a[:]
    base = 10
    max_val = max(out)
    exp = 1  # current digit place: 1, 10, 100, ...
    while max_val // exp > 0:
        # Stable counting sort on digit (x // exp) % base.
        buckets: List[List[int]] = [[] for _ in range(base)]
        for x in out:
            buckets[(x // exp) % base].append(x)  # appends preserve order → stable
        out = [x for bucket in buckets for x in bucket]  # concatenate in order
        exp *= base
    return out

Part 8 — quickselect (find the kth smallest without fully sorting: avg O(n))

Quicksort's partition tells you the pivot's final sorted index. If that index == k you're done; otherwise recurse into only the side containing k. Recursing one side (not both) gives the recurrence T(n) = T(n/2) + O(n) = O(n) average. Worst O(n²) (same bad-pivot risk as quicksort). Use it for "kth largest/smallest", "median", or "top-k by value" when you don't need the top-k sorted. k here is 0-indexed: k=0 → smallest.

def quickselect(a: List[int], k: int) -> int:
    if not (0 <= k < len(a)):
        raise IndexError("k out of range")
    a = a[:]
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        pivot = a[(lo + hi) // 2]
        i, j = lo, hi
        while i <= j:  # same partition as quicksort
            while a[i] < pivot:
                i += 1
            while a[j] > pivot:
                j -= 1
            if i <= j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        # Decide which side contains rank k and loop on just that side.
        if k <= j:
            hi = j
        elif k >= i:
            lo = i
        else:
            return a[k]  # k landed in the settled middle → it's the answer

If you need the top-k sorted, a heap is often cleaner. Every classic sort above can be verified by comparing its output against Python's sorted() on a spread of deterministic inputs: empty, single element, sorted, reverse-sorted, duplicates, negatives, and a pseudo-shuffled list.