Home/Sorting/Quick sort
Search algorithmsCTRL K

Quick sort

· divide and conquer · Lomuto partition
/sorting/quick-sort
COMPARISONS
0
≈ 1.39 n log₂ n expected
SWAPS
0
incl. pivot placements
DEPTH
0/ 9
recursion stack now / max
RANGE
[0, 23]
current partition
IN PLACE
0/ 24
final positions so far
comparingswappedpivotin place
n = 24 · seed 7 · 229 steps
step 0 / 228
Size24
quick_sort.ts
1
function quickSort(array: number[], low: number, high: number) {
2
  if (low >= high) return;
3
  const pivot = array[high];
4
  let i = low;
5
  for (let j = low; j < high; j++) {
6
    if (array[j] < pivot) {
7
      [array[i], array[j]] = [array[j], array[i]];
8
      i++;
9
    }
10
  }
11
  [array[i], array[high]] = [array[high], array[i]];
12
  quickSort(array, low, i - 1);
13
  quickSort(array, i + 1, high);
14
}
CURRENT STEP
line 1

Start: 24 values in random order. quickSort(a, 0, 23) is called on the whole range.

// how it works

Understanding Quick sort

quick sort · Lomuto partition · what the animation does not tell you
01

The idea

Quick sort picks one element as the pivot and rearranges the range so everything smaller sits on its left and everything larger on its right. After that partition the pivot is in its final position, and the algorithm calls itself on the two sides until every range has one element.

The Lomuto partition shown here uses the last element as the pivot and walks the range once, swapping smaller elements to the frontier i. Hoare’s version uses two indices closing in from both ends and does about three times fewer swaps.

02

The four stages

1
pivotchoose array[high]
2
partitionsmaller values go left of i
3
placeswap pivot to array[i], it is final
4
recurseboth sides, until 1 element
03

Complexity

best
O(n log n)pivots always in the middle
average
O(n log n)≈ 1.39 n log₂ n comparisons
worst
O(n²)already sorted input with a fixed pivot
space
O(log n)only the recursion stack
04

Versus its siblings

COMPARISONS AT N = 1 000
bubble
499,500
insertion
250,000
heap
17,000
quick
13,900
merge
8,700
log scale · random input · average of 100 runs
05

Pseudocode

QUICKSORT(array, low, high)
  if low ≥ high: return
  pivot ← array[high]; i ← low
  for j ← low to high − 1
    if array[j] < pivot: swap array[i], array[j]; i ← i + 1
  swap array[i], array[high]
  QUICKSORT(array, low, i − 1)
  QUICKSORT(array, i + 1, high)
06

When to use

In-memory arrays when stability does not matter: it is C’s qsort and the base of C++’s introsort.
When the extra memory of merge sort does not fit: quick sort sorts in place.
07

Pitfalls

Fixed pivot on sorted input hits the worst case. Random pivot or median-of-three fixes it.
Many equal values degrade Lomuto’s partition. Three-way partitioning, as in Dijkstra’s version, handles it.
Recursing into the larger side first can overflow the stack. Recurse on the smaller side and loop on the larger.
Not stable: equal values can swap order. Use merge sort or Tim sort when that matters.
08

History

Tony Hoare designed quick sort in 1959, at 25, while at Moscow State University working on machine translation and needing to sort dictionary words. He published it in 1961. In 2009 Vladimir Yaroslavskiy proposed the dual-pivot version that Java has used since version 7.

Back to Sorting