Quick sort visualization

Quick sort is a comparison-based sorting algorithm that picks a pivot, partitions the array so smaller values come before it and larger values after it, and then sorts each side recursively. It is an in-place divide and conquer sort with O(n log n) average time.

It does its work before the recursion instead of after, which is the opposite of merge sort.

How it works

1. If the range has fewer than two elements, it is already sorted: stop.
2. Choose a pivot. This lesson takes the last element.
3. Partition: scan the range and move values that are not greater than the pivot to the front, then swap the pivot into the gap.
4. The pivot is now in its final position. Sort the part to its left and the part to its right with the same steps.

A worked example of quick sort

Sort [8, 3, 7, 1, 5, 6, 4]. The last element of each range is the pivot:

1. Indexes 0 to 6, pivot 4 (6 comparisons): the pivot lands at index 2. [3, 1, 4, 8, 5, 6, 7]
2. Indexes 0 to 1, pivot 1 (1 comparison): the pivot lands at index 0. [1, 3, 4, 8, 5, 6, 7]
3. Indexes 3 to 6, pivot 7 (3 comparisons): the pivot lands at index 5. [1, 3, 4, 5, 6, 7, 8]
4. Indexes 3 to 4, pivot 6 (1 comparison): the pivot lands at index 4. [1, 3, 4, 5, 6, 7, 8]

The ranges that hold a single element, such as index 1 after step 2, are in place without a partition. In total: 11 comparisons and 18 writes. After partition 1, every value left of index 2 is at most 4 and every value right of it is at least 5, so the two sides never need to meet again.

Quick sort pseudocode

Indexes start at 0, as in the code of this lesson. The first call is QUICKSORT(A, 0, n - 1). PARTITION is the Lomuto scheme from Cormen et al., chapter 7.

QUICKSORT(A, lo, hi)
1  if lo < hi
2      p = PARTITION(A, lo, hi)
3      QUICKSORT(A, lo, p - 1)
4      QUICKSORT(A, p + 1, hi)

PARTITION(A, lo, hi)
1  pivot = A[hi]
2  i = lo - 1
3  for j = lo to hi - 1
4      if A[j] <= pivot
5          i = i + 1
6          exchange A[i] with A[j]
7  exchange A[i + 1] with A[hi]
8  return i + 1

The index i marks the end of the values that are at most the pivot. Line 7 puts the pivot right after them, and line 8 returns its final position.

Time and space complexity

If each pivot splits the range roughly in half, there are about log n levels and each level does O(n) work: O(n log n). If the pivot is always the smallest or largest value, one side is empty every time, the ranges shrink by only one, and the work becomes O(n²).

Complexity

Best case time	O(n log n)
Average case time	O(n log n)
Worst case time	O(n²)
Extra space	O(log n)

• Best and average time: O(n log n), because the splits are reasonably balanced.
• Worst time: O(n²), because every split is maximally unbalanced.
• Space: O(log n) for the recursion stack when the splits are balanced. A very unbalanced run can make the stack deeper.

Stability and memory

Quick sort sorts in place: it only swaps values inside the array. It is not stable, because the partition swaps can move equal values past each other.

When to use it, and when not to

• Use it for general in-memory sorting of arrays, where it is usually fast in practice because it moves data in place and has little overhead.
• Avoid it when you need a guaranteed O(n log n) bound or a stable result. Prefer merge sort then.

Where quick sort is used

• C++ std::sort. Common implementations, such as libstdc++, use introsort: quick sort that switches to heap sort when the recursion gets too deep, which gives the O(n log n) worst case the C++ standard requires. They also finish small ranges with insertion sort.
• Java's sort for primitive arrays. Arrays.sort on int[], double[] and the other primitive types uses a dual-pivot quick sort. For objects Java uses Timsort instead, because quick sort is not stable and objects can be equal yet distinguishable.
• Go's sort package. Since Go 1.19 it uses pattern-defeating quick sort, a version that detects patterns such as sorted input and avoids the bad cases described above.

The shared reason is speed on typical data: quick sort sorts in place, scans the array in order, and does little work per element.

Related algorithms and variations

The pivot rule decides the worst case. Choosing a random element, or the median of the first, middle and last elements, makes the sorted-input case harmless. Hoare's original partition scans from both ends and makes fewer swaps than the Lomuto version used here. A three-way partition groups values equal to the pivot in the middle, which fixes the all-equal input.

Quickselect, also from Hoare, partitions the same way but follows only the side that holds the position it wants, so it finds the k-th smallest value in O(n) time on average without sorting. For the other O(n log n) sorts, see merge sort (merge sort vs quick sort) and heap sort (quick sort vs heap sort).