Sorting

Why sorting is everywhere

A huge number of problems collapse the moment the input is sorted: it unlocks two pointers, binary search, greedy sweeps, deduplication, and grouping. So sorting is rarely the answer by itself — it’s the preprocessing step that makes the real algorithm trivial. That’s also why the cost of sorting, O(n log n), is the price of admission for so many solutions, and why knowing the algorithms underneath actually matters.

This article covers the algorithms themselves — not just how to call sorted() — because interviewers ask you to implement and compare them, and the trade-offs (stable? in-place? worst case?) drive real design choices.

The comparison-sort lower bound

Any sort that works by comparing pairs of elements cannot do better than Ω(n log n) in the worst case. The argument: there are n! possible orderings, each comparison gives one bit (≤ or >), and you need enough bits to distinguish all n! outcomes — so at least log₂(n!) ≈ n log n comparisons. This is why merge/quick/heap sort all land at O(n log n), and why beating it (counting/radix) requires not comparing elements at all.

Two properties to track for every sort

• Stable — equal elements keep their original relative order. Critical when you sort by one key after another (sort by name, then stably by age → grouped by age, alphabetical within). Merge sort is stable; quicksort and heapsort are not.
• In-place — uses only O(1) (or O(log n)) extra space. Quicksort and heapsort are in-place; standard merge sort needs O(n) scratch space.

Most “which sort?” decisions come down to these two plus the worst-case guarantee.

Insertion sort — the small-input workhorse

Build the sorted portion one element at a time, shifting larger elements right to insert each new one into place.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # shift bigger elements right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

• Time: O(n²) worst/average, but O(n) on nearly-sorted input.
• Space: O(1), in-place and stable.
• Why it matters: it’s the fastest option for small arrays (low constant factor), so real library sorts switch to it for subarrays below ~16 elements. Selection sort and bubble sort are the same O(n²) tier but strictly worse in practice — know them, don’t use them.

Merge sort — the stable, predictable divide-and-conquer

Split the array in half, recursively sort each half, then merge the two sorted halves into one.

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, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # `<=` keeps it STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

• Time: O(n log n) in all cases — no bad inputs. (log n levels of recursion, O(n) merge work per level.)
• Space: O(n) scratch for the merge — its main drawback.
• Stable: yes (with <= in the merge).
• Where it wins: when you need a guaranteed O(n log n) and stability; sorting linked lists (merge needs no random access, O(1) extra); and external sorting of data too big for RAM (merge sorted chunks streamed from disk). The merge step itself solves counting inversions and reverse pairs — count cross-pairs while merging.

Quicksort — the in-place average-case champion

Pick a pivot, partition the array so everything ≤ pivot is left and everything > pivot is right, then recurse on each side. The pivot lands in its final position each partition.

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):              # Lomuto scheme, pivot = last element
    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

• Time: O(n log n) average, but O(n²) worst case — when partitions are maximally unbalanced (e.g. already-sorted input with a naive last-element pivot).
• Space: O(log n) for recursion; in-place (no extra array).
• Stable: no.
• Beating the worst case: choose the pivot well — randomized pivot, or median-of-three (first/middle/last). For many equal keys, use 3-way partitioning (Dutch National Flag: < | = | >) to avoid O(n²) on duplicates.
• Where it wins: general-purpose in-memory sorting — excellent cache behavior and low constants make it the fastest in practice on average, which is why it’s the basis of most library sorts for primitives.

Heap sort — guaranteed O(n log n), in-place

Build a max-heap from the array, then repeatedly swap the max (root) to the end and sift down the reduced heap. (See the heaps primer for the heap mechanics.)

• Time: O(n log n) in all cases (O(n) to build the heap, n × O(log n) extractions).
• Space: O(1) — in-place.
• Stable: no.
• Where it wins: when you need both a worst-case O(n log n) guarantee and O(1) space — the only common sort that gives both. In practice it’s slower than quicksort (poor cache locality), so it’s often used as the fallback that rescues quicksort from its O(n²) worst case (see introsort below).

Non-comparison sorts — breaking the n log n barrier

When keys are integers in a bounded range (or fixed-width), you can sort in linear time by not comparing elements:

• Counting sort — tally how many times each value occurs, then emit values in order. O(n + k) for keys in [0, k). Stable if you fill output back-to-front from a prefix-sum of counts. Great when k = O(n).

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

• Radix sort — apply a stable counting sort digit by digit (least significant first). O(d · (n + b)) for d digits in base b. Sorts large integers/strings in linear time when d is small.

• Bucket sort — distribute values into buckets by range, sort each bucket, concatenate. O(n) when input is uniformly distributed. Powers Top-K Frequent and Sort Characters by Frequency (bucket by count).

The catch: these need bounded, integer-like keys and extra space — they don’t generalize to arbitrary comparables.

What the language actually runs

You’ll rarely hand-roll these, so know what’s under sort():

• Python sorted/list.sort, Java Arrays.sort (objects) → Timsort: a hybrid of merge sort and insertion sort that exploits already-sorted “runs.” Stable, O(n log n) worst, O(n) on nearly-sorted data.
• C++ std::sort → introsort: quicksort that switches to heapsort when recursion goes too deep (guarding the O(n²) worst case) and to insertion sort on small subarrays. Not stable; std::stable_sort is the merge-based variant.

The pattern in both: quicksort/merge for the bulk, insertion for the small, heapsort as a worst-case guard. That hybrid is the practical state of the art.

Custom order with keys and comparators

Sort by any derived value; for multi-key order, return a tuple (compared left-to-right):

people.sort(key=lambda p: (-p.height, p.age))   # tallest first, then youngest

Because Python’s sort is stable, you can also sort in passes: sort by the secondary key, then by the primary. For comparisons that aren’t a simple key (pairwise rules), wrap with functools.cmp_to_key — the classic Largest Number problem sorts by comparing concatenations a+b vs b+a.

Quickselect — the k-th element without a full sort

Partition like quicksort, but recurse into only the side that contains the k-th position — so you never sort the rest. Expected O(n) (vs O(n log n) for a full sort) for Kth Largest Element and Median of an unsorted array:

import random
def quickselect(nums, k):              # k-th smallest, 0-indexed
    pivot = random.choice(nums)
    lo = [x for x in nums if x < pivot]
    eq = [x for x in nums if x == pivot]
    hi = [x for x in nums if x > pivot]
    if k < len(lo):
        return quickselect(lo, k)
    if k < len(lo) + len(eq):
        return pivot
    return quickselect(hi, k - len(lo) - len(eq))

Worst case is O(n²) (bad pivots); randomization makes that astronomically unlikely. The deterministic median-of-medians pivot guarantees O(n) but has high constants, so it’s mostly theoretical.

The comparison table

Choosing in an interview

• “Just sort it” → call the library sort (Timsort/introsort), note it’s O(n log n).
• Need stability (sorting by multiple keys) → merge sort / stable_sort.
• Tight on memory, need a guarantee → heap sort.
• Keys are small integers → counting/radix for O(n).
• Only need the k-th element or top-K → quickselect (O(n)) or a heap, not a full sort.
• Asked to implement one → merge sort (cleanest correctness story) or quicksort (in-place; be ready to discuss pivot choice and the O(n²) worst case).

Always state the stability and worst-case properties when you pick — those are the discriminators interviewers are listening for. See the divide-and-conquer primer for the recursion patterns behind merge sort and quickselect, and the heaps primer for the heap that powers heap sort.