Sorting Foundations

You will rarely implement a sort in production — your language ships a superb one — but sorting is where you build intuition for how algorithms move data, and it comes up constantly as a subroutine. Understanding the mechanics also explains why the standard library sort has the complexity it does.

Insertion sort: how humans sort cards

Insertion sort keeps a growing sorted prefix on the left. Each step takes the next unsorted element and slides it left until it lands in the right place — exactly how most people sort a hand of playing cards.

Watch the green prefix grow one element at a time. The orange highlights show the comparisons and shifts needed to open a gap for the incoming value. When the input is already nearly sorted, each element barely moves — insertion sort is O(n) in the best case, which is why real-world sorts use it for small or almost-sorted ranges.

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

Its worst case is O(n²) — a reverse-sorted array makes every element travel the full width. That’s fine for tiny arrays and disastrous for large ones.

The complexity landscape

O(n log n) is the floor for any comparison-based sort — you cannot do better in general, because distinguishing all n! orderings requires at least that many comparisons.

What your standard library actually does

Production sorts are hybrids. Python’s Timsort and many others detect already-sorted “runs” and use insertion sort for small chunks, then merge them — getting O(n) on friendly inputs and O(n log n) guaranteed on hostile ones. Knowing this lets you answer “what sort does your language use?” with more than a shrug.

Stability matters more than you’d think

A stable sort preserves the relative order of equal elements. That’s what makes multi-key sorting work: sort by name, then by department, and people stay alphabetized within each department. Reach for a stable sort whenever you sort by one key after another.

Practical rule: never hand-roll a sort in an interview unless asked. Call the library sort, state that it’s O(n log n), and spend your energy on the part of the problem that’s actually interesting.

Pattern recognition

Variations

Worked problems

These are sorting patterns, not sorting implementations. The interview signal is choosing the invariant that sorted order gives you.

def sort_colors(nums):
    lo, i, hi = 0, 0, len(nums) - 1

    while i <= hi:
        if nums[i] == 0:
            nums[lo], nums[i] = nums[i], nums[lo]
            lo += 1
            i += 1
        elif nums[i] == 2:
            nums[i], nums[hi] = nums[hi], nums[i]
            hi -= 1
        else:
            i += 1

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []

    for start, end in intervals:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)

    return merged

from functools import cmp_to_key


def largest_number(nums):
    parts = [str(x) for x in nums]

    def compare(a, b):
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0

    parts.sort(key=cmp_to_key(compare))
    if parts[0] == "0":
        return "0"
    return "".join(parts)