Quicksort

Cost and properties

average	~1.39 n lg n compares
worst case	~n²/2 (shuffling makes it negligible)
in place	yes — no aux array
stable	no

Reference: Sedgewick & Wayne, §2.3; Hoare 1961.

Quicksort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import random

def sort(a):
    random.shuffle(a)                     # THIS is the performance guarantee
    _sort(a, 0, len(a) - 1)
    return a

def _sort(a, lo, hi):
    if hi <= lo:
        return
    j = partition(a, lo, hi)              # a[j] lands in its final place
    _sort(a, lo, j - 1)                   # sort the small keys
    _sort(a, j + 1, hi)                   # sort the large keys

def partition(a, lo, hi):
    pivot = a[lo]
    i, j = lo, hi + 1
    while True:
        i += 1
        while i < hi and a[i] < pivot:     # scan right past small keys
            i += 1
        j -= 1
        while j > lo and a[j] > pivot:     # scan left past large keys
            j -= 1
        if i >= j:                        # pointers crossed: done
            break
        a[i], a[j] = a[j], a[i]           # both stopped: swap them
    a[lo], a[j] = a[j], a[lo]             # pivot into position j
    return j

Why it works

The partitioning invariant

Take a[lo] as the pivot. Scan i right while keys are smaller, scan j left while keys are larger; when both stop, the two offending keys are on the wrong sides, so swap them. When the pointers cross, swap the pivot into a[j]. Now a[j] is in its final position — everything left is ≤ it, everything right is ≥ it — and neither recursive call ever touches it again.

Why quicksort wins in practice

It uses no auxiliary array and its inner loop is a tight scan over contiguous memory, so it makes far better use of cache than mergesort's copying. It does about 39% more compares than mergesort on average, and is still faster — a reminder that compare counts are a model, not a measurement.

The shuffle is not optional

On a sorted or reverse-sorted array, taking a[lo] as pivot splits off one key at a time: n²/2 compares and recursion n deep (which will overflow the stack). Shuffling first makes the input random regardless of where it came from, so the quadratic case becomes vanishingly unlikely — the guarantee is probabilistic, and it is bought by that one line.

Details worth copying

• Recur on the smaller side first to bound stack depth at lg n.
• Cut off to insertion sort for ranges under ~10 keys.
• Equal keys are the real trap: the scans stop on keys equal to the pivot. That looks wasteful but it is what keeps the split balanced; scanning past them makes an array of all-equal keys quadratic. If duplicates are common, use 3-way partitioning instead.

What to try in the animation

The animation skips the shuffle so the steps are predictable. Try already sorted to see the quadratic worst case the shuffle is there to prevent, and all equal to see why 3-way partitioning exists.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• MERGESORTEXAMPLE — M E R G E S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1
• all equal — 5 5 5 5 5 5 5 5
• few distinct — 2 1 3 1 2 3 1 2 3 1

Open Quicksort in the player →

The rest of Quicksort

• Quickselect Partition, then recur on the one side that can contain the answer.
• 3-way quicksort Partition into less-than, equal-to and greater-than.