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
1/67

Quick sort, 12 values in random order.

Counters

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

Settings

More options
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

Scroll the table sideways for the rest of the columns.

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

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.

The pivot is the whole algorithm. Everything else about quicksort is the same partition loop, and every real implementation differs only in how it chooses that pivot and when it gives up and calls something else. Introsort counts its own recursion depth and switches to heapsort past 2·log n levels, which is how a language's standard library promises O(n log n) while still running quicksort almost all of the time.

Check yourself

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