programmingconcepts

§ 3.6 · Algorithms

Quicksort

Pick a pivot, move every smaller value to its left, then sort each side the same way.

Quicksort picks a pivot value, moves every smaller value to its left and every larger value to its right, then sorts each side the same way. It averages O(n log n) time and sorts in place, which makes it fast in practice. With bad pivots, such as always the first value on sorted input, it falls to O(n²).

Average
O(n log n)
Worst
O(n²)
Extra space
O(log n)
Stable
No
In place
Yes
Requires
RecursionBig O
def quicksort(a, lo, hi):
    if lo >= hi:
        return
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    quicksort(a, lo, i - 1)
    quicksort(a, i + 1, hi)

Press Play or Step to start.

0 comparisons0 swapsstep 0 / 00 / 16 in placecomparingmovingpivot

Fig. 3.6. The highlighted line is the one running now. Blue bars are being compared, orange bars are moving, the dark grey bar is the pivot, and black bars have reached their final place.

Intuition

Picture sorting a stack of exam papers. Pick one score, make a pile of everything lower and a pile of everything higher, then repeat on each pile until every pile has one paper.

Quicksort does exactly that, inside the array itself. One pass puts the pivot where it will sit in the finished list. Everything left of it is smaller, everything right of it is not, and the two sides never need to meet again.

How it works

The figure uses the Lomuto partition, the easiest version to follow:

  1. Take the last value in the range as the pivot.
  2. Walk j from the start of the range to just before the pivot. Keep a second index, i, marking where the next small value should go.
  3. Each time a[j] is smaller than the pivot, swap it into position i and move i one step right.
  4. When the walk ends, every value before i is smaller than the pivot. Swap the pivot into position i: that is its final place.
  5. Sort the part left of i and the part right of i the same way. A range of zero or one values is already sorted.

Step through the figure and watch the code: the comparison line lights up blue, and the two swap lines light up orange.

Complexity

Case Time When it happens
Best O(n log n) Every pivot splits its range roughly in half.
Average O(n log n) Random input. Uneven splits even out over many partitions.
Worst O(n²) The pivot is always the smallest or largest value, such as already sorted input with a last-element pivot.

Each level of recursion does about n comparisons in total. Balanced splits give about log₂ n levels, and lopsided ones give up to n levels. The extra space is the recursion stack: about log n deep on average, but n deep in the worst case unless the code always recurses into the smaller side first.

Common mistakes

  1. No base case. The recursion must stop on ranges of size 0 or 1.
  2. Recursing on a range that still includes the pivot. The range never shrinks, so the sort never finishes.
  3. Assuming it is stable. Equal values can swap order. Use a merge sort when that matters.
  4. A fixed pivot on sorted data. Always taking the last value turns already-sorted input into the worst case.

When to use it

Use quicksort when you sort arrays in memory and want speed with little extra space. It reads memory in order, which caches handle well, and on random data it is usually faster than merge sort in practice.

Avoid a hand-written quicksort when the order of equal values matters, when an attacker could choose the input to force the worst case, or when you are sorting a linked list. In real code, call your language’s built-in sort, which already guards against these cases.

In other languages

Language Built-in sort Uses quicksort?
Python list.sort(), sorted() No: a stable merge sort (Timsort family)
JavaScript Array.prototype.sort() No: stable since ES2019; engines use merge-based sorts
Java Arrays.sort(int[]) Yes: dual-pivot quicksort for primitives. Objects use a stable merge sort
C qsort() Not guaranteed: the standard doesn’t name an algorithm
Go slices.Sort() Yes: pattern-defeating quicksort (pdqsort)
Rust sort_unstable() Yes: a quicksort variant. sort() is a stable merge sort

Check yourself

Check yourself

Partition [7, 2, 9, 4, 5] using the last value, 5, as the pivot. Where does 5 end up?

Check yourself

This quicksort sorts [1, 2, 3, 4, 5], which is already in order. How many comparisons does it make?

Sources

  • C. A. R. Hoare, “Quicksort,” The Computer Journal 5, no. 1 (1962): 10–16.
  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 7, “Quicksort.”

Newsletter

One new concept each week, by email.

Signup opens soon.