Sorting Algorithms

How Quicksort Works

Quicksort picks a pivot, moves everything smaller to its left and everything larger to its right, and recurses on both sides. Fast in practice, quadratic if the pivot is chosen badly.

  • Waiting
  • Being compared
  • Just moved
  • In final position
Speed

Step 1 of 67

Quick sort, 12 values in random order.

Counters

Comparisons
0
Writes
0
n
12
Average case
O(n log n)

Settings

Starting order

Two to 48 numbers. Sorted in exactly the order you type them.

Quick sort

  1. 1stack = [(0, n-1)]
  2. 2while stack not empty:
  3. 3 (lo, hi) = stack.pop()
  4. 4 pivot = a[hi]
  5. 5 i = lo
  6. 6 for j in lo..hi-1:
  7. 7 if a[j] <= pivot:
  8. 8 swap(i, j); i += 1
  9. 9 swap(i, hi) // pivot final
  10. 10 push (lo, i-1) and (i+1, hi)

The same array, every algorithm

Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.

  1. Merge3344 writes
  2. Quick3340 writes
  3. Insertion4042 writes
  4. Shell4637 writes
  5. Heap5166 writes
  6. Bubble6062 writes
  7. Selection6618 writes

How the seven compare

AlgorithmBestAverageWorstExtra memoryStable
BubbleO(n)O(n²)O(n²)O(1)Yes
InsertionO(n)O(n²)O(n²)O(1)Yes
SelectionO(n²)O(n²)O(n²)O(1)No
ShellO(n log n)O(n√n)O(n²)O(1)No
MergeO(n log n)O(n log n)O(n log n)O(n)Yes
QuickO(n log n)O(n log n)O(n²)O(log n)No
HeapO(n log n)O(n log n)O(n log n)O(1)No

Stable means equal values keep their original order.

Complexity

BestAverageWorstExtra memory
O(n log n)O(n log n)O(n²)O(log n)

The worst case is a pivot that splits off one element at a time — which is exactly what a first-element pivot does to already sorted input. Random or median-of-three pivots make it vanishingly unlikely.

How quicksort works

Quicksort chooses one element as a pivot and partitions the range so that smaller values end up before it and larger ones after it. The pivot is then in its final position, and the two sides are sorted the same way. It does less data movement than merge sort and needs no buffer, which is why it is usually the faster of the two in memory despite the worse bound.

  1. Choose a pivot from the range. The middle or a random element is a reasonable choice; the first element is not.
  2. Partition: walk in from both ends, swapping any pair that is on the wrong side of the pivot.
  3. The pivot is now in its final position and never moves again.
  4. Recurse on the left part and the right part, ignoring the pivot itself.
  5. Stop when a part has fewer than two elements.

Implementation

The same algorithm the visualiser is running, written to be read.

def quicksort(values, low=0, high=None):
    if high is None:
        high = len(values) - 1
    if low >= high:
        return values

    # Middle as pivot: a first-element pivot turns sorted input into O(n^2).
    pivot = values[(low + high) // 2]
    i, j = low, high
    while i <= j:
        while values[i] < pivot:
            i += 1
        while values[j] > pivot:
            j -= 1
        if i <= j:
            values[i], values[j] = values[j], values[i]
            i += 1
            j -= 1

    quicksort(values, low, j)
    quicksort(values, i, high)
    return values

When to use it

  • Use it as a default in-memory sort for primitives: good cache behaviour, no allocation, and a small constant factor.
  • Use it with a random or median-of-three pivot, and switch to insertion sort for small ranges — that combination is what most standard libraries ship.
  • Avoid it when you need a worst-case guarantee or stability. Introsort's answer is to watch the recursion depth and fall back to heapsort.

Check yourself

If the animation made sense, these should too.

Why is a first-element pivot a bug rather than a style choice?

On already sorted or reverse sorted input it splits off one element per level, giving n levels instead of log n - O(n²) time and O(n) stack. Sorted input is extremely common, so the worst case stops being hypothetical. A middle, random or median-of-three pivot avoids it.

Quicksort's worst case is worse than merge sort's. Why is it usually faster anyway?

It sorts in place, so there is no buffer to allocate and no copying between arrays, and partitioning walks memory linearly, which the cache rewards. Merge sort's guarantee costs an O(n) buffer and twice the data movement.

More sorting algorithms