Sorting

Sorting

From quadratic swaps to n log n divide and conquer

~13 minLesson 9 of 25Written by Claude Opus 4.8

Putting things in order sounds trivial - until you count the work. A schoolbook method compares every pair and costs $O (n^{2})$ ; the clever ones halve-and-conquer for $O (n lo g n)$ . For a million items that gap is fifty-thousand-fold. Sorting is where you first feel, in your bones, that the choice of algorithm matters more than the speed of the machine.

Two families, one job

Every sort here answers the same question - which order? - but in two very different ways. The elementary sorts (bubble, selection, insertion) use two nested loops and land at

O (n^{2})

. The divide-and-conquer sorts (merge, quicksort, heapsort) break the problem into halves and reach

O (n lo g n)

. Three properties tell them apart: how fast they are, whether they need extra memory, and whether they're stable.

The line-up, at a glance

Three words before the table. means equal keys keep their original relative order - vital when you sort by one field after another. means $O (1)$ extra memory (beyond the recursion stack). And means already-ordered input runs faster - a property only some sorts have.

Algorithm	Best	Average	Worst	Extra space	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
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	no
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	no

Read that table as a set of trade-offs, not a ranking. Merge sort guarantees $O (n lo g n)$ and stability, but rents $O (n)$ scratch memory to merge. Quicksort sorts in place and is usually fastest in practice, but a bad pivot can drag it to $O (n^{2})$ . Heapsort guarantees $O (n lo g n)$ and sorts in place - its price is poor cache behaviour and no stability. There is no free lunch.

Race the algorithms yourself

Pick an algorithm and press Run (or Step through one operation at a time). Bars are array values; amber marks a comparison, red a swap / write, green a value now in its final place. Watch the two counters - comparisons and swaps - tell the real cost story.

Sorting race arena - choose an algorithm, then Run or Step and watch the counters.

unsortedcomparingswap / writepivotin final place

algorithmspeed

input:

0comparisons

0swaps

Bubble: O(n²) average & worst, O(n) if already sorted (early exit) · in-place · stable.

Choose an algorithm and press Run - or Step through one operation at a time.

Now break quicksort - the "already sorted" trap

Select Quicksort, then click Already sorted, then Run. Watch it grind: this pivot is always the last (largest) element, so every partition peels off just one item and recurses on the remaining

n - 1

. That's

n + (n - 1) + \dots + 1 \approx n^{2} /2

comparisons - 66 for our 12 bars, exactly what selection sort costs and six times what insertion sort needs. An already-sorted array is quicksort's worst case. Real libraries dodge it by choosing a random or median-of-three pivot.

Selection is not adaptive - insertion is

Run Selection sort on the already-sorted input: still 66 comparisons, because it rescans the whole remaining tail every time regardless of order. Now run Insertion sort on the same input: just 11 comparisons, zero swaps. Insertion (and early-exit bubble) is adaptive - nearly-sorted data is its best case,

O (n)

. That's why insertion sort is the workhorse inside real hybrid sorts for small or almost-ordered chunks.

Merge vs. quick vs. heap, in one breath

Merge sort divides the array in half, sorts each half, then merges two sorted runs by repeatedly taking the smaller front element - the merge is where all the work lives. Quicksort flips the order: it partitions around a pivot so everything smaller sits left and larger sits right, then recurses - the partition does the work and the "merge" is free. Heapsort builds a binary heap, then repeatedly pops the maximum to the end. Here is quicksort's engine, the Lomuto partition our demo uses:

def quicksort(a, lo, hi):
    if lo >= hi:                          # 0 or 1 elements: already sorted
        return
    p = partition(a, lo, hi)              # pivot lands at its FINAL index p
    quicksort(a, lo, p - 1)               # sort the left region
    quicksort(a, p + 1, hi)               # sort the right region

def partition(a, lo, hi):
    pivot = a[hi]                         # LAST element as pivot (Lomuto)
    i = lo - 1                            # boundary of the "<= pivot" region
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]       # grow the small region
    a[i + 1], a[hi] = a[hi], a[i + 1]     # drop the pivot between the two regions
    return i + 1                          # a sorted array makes every split n-1 / 0 -> O(n^2)

Quicksort - where the pivot does its work.

Why $O (n lo g n)$ is a wall

No comparison-based sort - one that learns about order only by asking "is $a$ before $b$ ?" - can beat $O (n lo g n)$ in the worst case. The argument is short and beautiful, and it comes straight from logarithms.

The counting argument (the light version)

A sort must be able to produce any of the $n!$ possible orderings of its input. Each comparison has two outcomes, so a sequence of $h$ comparisons can distinguish at most $2^{h}$ arrangements - a binary decision tree of height $h$ has at most $2^{h}$ leaves. To tell apart all $n!$ inputs we therefore need

2^{h} \geq n! ⟹ h \geq lo g_{2} (n!) .

Stirling's approximation gives $lo g_{2} (n!) \approx n lo g_{2} n - n lo g_{2} e = Θ (n lo g n)$ . So every comparison sort needs $Ω (n lo g n)$ comparisons in the worst case - merge and heapsort already sit on that floor. (Non-comparison sorts like counting or radix sort escape it by not comparing keys - a story for another day.)

Check yourself

Why can quicksort degrade to O(n²) on an already-sorted array?

What sets the O(n log n) floor for comparison-based sorting?

Which common sorts are O(n log n) in the worst case, and which of them needs extra memory?

Pin down the worst-case guarantees and the memory cost together. Try to state it, then check.

Lock it in

Elementary sorts (bubble, selection, insertion) cost $O (n^{2})$ ; divide-and-conquer sorts (merge, quick, heap) reach $O (n lo g n)$ .
The table is trade-offs, not a ranking: speed, extra memory, and stability each pull a different way.
A last-element pivot makes an already-sorted array quicksort's $O (n^{2})$ worst case; insertion sort is adaptive and hits $O (n)$ on the same input.
No comparison sort beats $O (n lo g n)$ : distinguishing all $n!$ orderings needs $lo g_{2} (n!)$ comparisons.

Primary source

Drive every one of these on your own input at VisuAlgo - Sorting, the reference visualiser for exactly this material. For the derivations by hand - the recurrences, the

n lo g n

lower bound, the partition invariants - work through Abdul Bari's sorting playlist.

Ask your teacher

Want the merge-sort recurrence

T (n) = 2 T (n /2) + O (n)

solved with the Master Theorem, or how real libraries build hybrids (Timsort, introsort) from these pieces? Ask and I'll build the follow-up. A tie-in worth planting now, spelled out in sorting and selection to top-k sampling in the LLM course: decoding an LLM is a selection problem, not a full sort. Top-k sampling needs only the

k

largest logits, not all of them ranked - a heap or quickselect finds them in

O (n lo g k)

instead of the

O (n lo g n)

a full sort would waste. Same partition idea you just watched, stopped early.

The line-up, at a glance

Race the algorithms yourself

Merge vs. quick vs. heap, in one breath

Why O(nlogn) is a wall

Check yourself

Why $O (n lo g n)$ is a wall