🧩 Data Structures & Algorithms · Chapter 11

Sorting algorithms

Every sort ends with the same list. What differs is how many comparisons it took, how much memory it borrowed, and whether equal items kept their order.

Study this lesson free in the app →

The basics

A sorting algorithm rearranges items into order — smallest to largest, A to Z, oldest to newest.

The problem it solves: sorted data is what makes everything else fast. Binary search, finding duplicates, merging two lists, the median, "top 10" — all are easy once data is sorted. So the cost of sorting is paid constantly, and the choice of algorithm decides whether 1 million items take a fraction of a second or many minutes.

The mental model: two ways people sort a hand of playing cards. Pick up one card at a time and slide it into place among the cards you already hold — that's insertion sort, O(n²) but great when the hand is nearly sorted. Or split the deck between friends, have each sort their half, then merge the two sorted piles by repeatedly taking the smaller top card — that's merge sort, O(n log n).

Explained

Sort 1,000,000 numbers with an O(n²) algorithm: about 500 billion comparisons. Minutes to hours.

With an O(n log n) one: about 20 million. A blink.

Same result, 25,000× less work. Below you'll watch four algorithms sort the same seven numbers — compare how each one moves.

Two ways to sort exam papers

A teacher has 40 marked papers to put in score order.

Way 1 — the card player. Take papers one at a time and slide each into its place in the sorted pile in your hand. If the papers were almost in order already, each one barely moves. If they were reversed, each one travels all the way down. That's insertion sort.

Way 2 — the team. Split the stack between two assistants, who split theirs again… until everyone holds one paper (already sorted!). Then pairs merge: look at the two top papers, take the lower one, repeat. Merging two sorted piles is a single pass. That's merge sort — it needs a table to lay the merged pile on (extra space), but it's fast no matter how messy the stack was.

Bubble sort: big values float right

Compare neighbours, swap if out of order. After each pass the largest remaining value has bubbled to the end. O(n²) comparisons; an early-exit check (no swaps in a pass → stop) makes it O(n) on sorted input.

Insertion sort: grow a sorted prefix

Take the next item and shift bigger items in the sorted prefix one step right until its slot appears. Each item moves only as far as it's out of place — so nearly-sorted data finishes in about n steps.

Merge sort: split, then merge

Halve until single items, then merge sorted halves back together. log₂ n levels of splitting, n work to merge each level → O(n log n), whatever the input. The merged output needs its own buffer: O(n) extra space.

Quick sort: place the pivot, recurse

Pick a pivot, move smaller values to its left and larger to its right — now the pivot is in its final place. Recurse on both sides. Good pivots split evenly (O(n log n)); a pivot that's always the smallest or largest leaves one side empty (O(n²)).

The comparison table

            best        average     worst       extra   stable
──────────────────────────────────────────────────────────────
bubble*     O(n)        O(n²)       O(n²)       O(1)    yes
selection   O(n²)       O(n²)       O(n²)       O(1)    no
insertion   O(n)        O(n²)       O(n²)       O(1)    yes
merge       O(n log n)  O(n log n)  O(n log n)  O(n)    yes
quick       O(n log n)  O(n log n)  O(n²)       O(log n) no
heap        O(n log n)  O(n log n)  O(n log n)  O(1)    no
Timsort     O(n)        O(n log n)  O(n log n)  O(n)    yes
counting    O(n + k)    O(n + k)    O(n + k)    O(n + k) yes

\* with the 'stop if no swaps' check. k = range of key values.

Why quick sort is still popular despite its worst case: it works in place and touches memory sequentially, so it's often fastest in practice. Libraries pick pivots randomly or by median-of-three to make O(n²) vanishingly unlikely.

Insertion and merge sort in Python

def insertion_sort(a):
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:   # strict > keeps equal items in order
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= takes from the left first → stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

# In real code:
people = [("Ana", 31), ("Ben", 25), ("Chen", 31)]
sorted(people, key=lambda p: p[1])         # Ben, Ana, Chen — Ana stays before Chen
sorted(people, key=lambda p: (-p[1], p[0]))  # age desc, then name

Words to know

In two minutes

• Simple sorts (bubble, selection, insertion) are O(n²) time and O(1) space; fine for tiny or nearly-sorted inputs.
• Insertion sort is O(n) on already-sorted data and stable — real libraries use it for small chunks.
• Merge sort: split in half, sort each, merge. O(n log n) in every case, O(n) extra space, stable.
• Quick sort: partition around a pivot, recurse on each side. O(n log n) average, O(n²) worst with bad pivots, O(log n) stack space, not stable.
• Heap sort: O(n log n) worst case with O(1) extra space, but not stable and slower in practice.
• Any comparison sort needs Ω(n log n) comparisons in the worst case; counting/radix sort go below by exploiting small integer keys.
• In real code use the built-in: Python's sorted() is Timsort — stable, O(n log n) worst, O(n) on sorted runs, O(n) extra space.

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.