Free explainer · Video · Code · Quiz
Quick Sort
Pick a pivot, push smaller values left and bigger values right, then sort each side the same way. In-place quick sort with Hoare partition, a median-of-three pivot and an O(log n) stack.
- Difficulty
- Medium
- Time
- O(n log n) avg, O(n²) worst
- Space
- O(log n)
Try it yourself
Step through it at your own pace — this is Quick Sort Animation, running right on the page.
LiveQuick Sort Animation
Loading the preview…
How it works
The idea, a worked example, and the traps to avoid.
The idea
You're sorting a messy stack of exam papers by score. Pull one out, say a 70. Lower scores go in a pile on the left, higher ones on the right. Nothing is sorted yet, but the 70 now sits between the piles, and each pile is a smaller version of the same job. Repeat on each pile until every pile holds one paper.
That's quick sort, a divide and conquer algorithm. The chosen value is the pivot, and splitting around it is partitioning. Merge sort does its real work when it joins halves; quick sort does it when it splits, so nothing needs joining afterwards.
Walkthrough
Sort [7, 2, 9, 4, 3, 8, 1].
Pick the pivot. Look at the first, middle and last values: 7, 4 and 1. Put those three in order inside the array. That gives [1, 2, 9, 4, 3, 8, 7], and the middle one, 4, is the pivot.
Partition (Hoare's scheme). A pointer i walks right from the start and stops at a value that is ≥ 4. A pointer j walks left from the end and stops at a value that is ≤ 4. If they haven't crossed, both values sit on the wrong side, so swap them and keep going.
| Round | i stops at | j stops at | Action | Array |
|---|---|---|---|---|
| 1 | index 2 (9) | index 4 (3) | swap 9 and 3 | [1, 2, 3, 4, 9, 8, 7] |
| 2 | index 3 (4) | index 3 (4) | pointers met, split at 3 | [1, 2, 3, 4 │ 9, 8, 7] |
Everything in [0..3] is ≤ 4 and everything in [4..6] is ≥ 4. Sort both sides the same way and the whole array is sorted. Note that both sides are inclusive: with Hoare's scheme you recurse on [lo, split] and [split + 1, hi].
The choices in this code
Hoare instead of Lomuto. Lomuto's partition, the one in many textbooks, is easier to read but makes about three times as many swaps. Worse, on an array of identical values every split is "everything" versus "nothing", and the sort turns O(n²). Hoare's pointers stop on values equal to the pivot and swap them, so duplicates spread over both sides and an all-equal array splits down the middle.
Median-of-three pivot. Always taking the first element is the classic trap: on already sorted input, the most common "real" input there is, every split peels off one element and the sort goes quadratic. On sorted or reversed input the median of first, middle and last is the true median, so that case becomes the best case. A random pivot also works (O(n log n) expected on any input); we stay deterministic so every run takes the same steps.
Recurse on the smaller side, loop on the bigger one. Each recursive call gets at most half of the range, so the stack never goes deeper than about log₂ n frames, even with unlucky pivots. Naive recursion can need n frames and crash on big inputs.
Why it's correct
During partitioning, everything left of i is ≤ pivot and everything right of j is ≥ pivot. Each swap fixes two out-of-place values at once. When the pointers cross, the range is split cleanly: every value in [lo, split] is ≤ every value in [split + 1, hi].
Both sides are non-empty, so each is strictly smaller than the range we started with, and the recursion must end. If each side ends up sorted, and every value on the left is no bigger than every value on the right, the whole range is sorted.
Complexity
- Average and best: O(n log n). Each level of recursion touches all n values once, and balanced splits give about log₂ n levels. Even a lopsided 10/90 split every time stays O(n log n), with a bigger constant.
- Worst: O(n²). If the pivot is always the smallest or largest value, each level shrinks by one element. Median-of-three removes the common cases (sorted, reversed, all equal), but crafted inputs can still trigger it. That's why C++'s
std::sortis an introsort: it switches to heap sort when the recursion gets too deep. - Space: O(log n) for the call stack. The sort itself works in place.
- Not stable. Hoare swaps values across long distances, so equal values can change order: even
[5a, 5b]comes out as[5b, 5a]. When that matters (sort by date, then by price), use a stable sort such as merge sort or Timsort.
In practice quick sort is often the fastest comparison sort for arrays: in place, a tiny inner loop, and memory read in order, which caches love.
Common bugs
- Lomuto habits in Hoare code. Recursing on
[lo, split - 1]skips an element. With Hoare it's[lo, split]and[split + 1, hi]. - Using
<=in the scans.while (values[i] <= pivot)can run past the end of the range, and it piles every duplicate onto one side. - Taking the pivot from the last index. With Hoare and floor division, the split can land on
hi. The right side is then empty and the recursion never ends. Our pivot comes frommid, which is always less thanhi. - Overflow in
(lo + hi) / 2in Java or C++. Uselo + (hi - lo) / 2.
You'll also meet a three-line Python version that builds lists of smaller, equal and bigger values. Great for showing the idea, but it copies the data at every level and isn't in place.
When to use it (and when not)
Use it for general in-memory sorting of numbers or keys, especially when memory is tight. Look elsewhere when you need a stable order (merge sort), a guaranteed worst case (heap sort or merge sort), or you're sorting a linked list (merge sort). For a handful of nearly sorted items, insertion sort wins. In real projects, call the built-in sort: it's a tuned hybrid of these ideas.
Interview variations
- Kth smallest or largest element (Quickselect). Partition once, then continue only into the side that contains position k. You skip half the work at every level, so it's O(n) on average instead of O(n log n).
- Sort colors / Dutch national flag. Partition into three groups,
< pivot,= pivotand> pivot, in one pass. This three-way partition is also the cure for inputs with many duplicates. - Top-k frequent words or k closest points. Quickselect on a key, either the frequency or the distance, gives the k best without fully sorting.
Code
The same algorithm, step for step, in 4 languages.
// Quick sort, in place: Hoare partition around a median-of-three pivot.
// Pick a pivot, move the small values left and the big values right, then sort each side.
/**
* Sorts `values` in ascending order, in place.
* Not stable: equal values may end up in a different order than they started.
*
* @param {number[]} values the array to sort
* @returns {void}
*/
export function quickSort(values) {
sortRange(values, 0, values.length - 1);
}
/**
* Sorts values[lo..hi] (both ends included).
* Recurses into the smaller side and loops on the bigger one, so the call stack never grows
* past about log2(n) frames — even when the pivots are unlucky.
*
* @param {number[]} values
* @param {number} lo
* @param {number} hi
*/
function sortRange(values, lo, hi) {
while (lo < hi) {
const split = hoarePartition(values, lo, hi);
const leftSize = split - lo + 1;
const rightSize = hi - split;
if (leftSize < rightSize) {
sortRange(values, lo, split); // small side: recursion
lo = split + 1; // big side: next turn of the loop
} else {
sortRange(values, split + 1, hi);
hi = split;
}
}
}
/**
* Hoare partition of values[lo..hi]. Returns `split` with lo <= split < hi such that
* every value in [lo, split] is <= every value in [split + 1, hi].
* Both sides are non-empty, so each one is strictly smaller than the range we started with.
*
* @param {number[]} values
* @param {number} lo
* @param {number} hi
* @returns {number}
*/
function hoarePartition(values, lo, hi) {
const pivot = medianOfThree(values, lo, hi);
let i = lo - 1;
let j = hi + 1;
while (true) {
// Walk i right past values that already belong on the left…
do {
i++;
} while (values[i] < pivot);
// …and j left past values that already belong on the right.
do {
j--;
} while (values[j] > pivot);
if (i >= j) return j; // the two walks met: everything is on its side
swap(values, i, j); // both are on the wrong side — trade places
}
}
/**
* Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
* On sorted or reversed input this picks the true median, which is exactly where
* "always take the first element" falls to O(n²).
*
* @param {number[]} values
* @param {number} lo
* @param {number} hi
* @returns {number}
*/
function medianOfThree(values, lo, hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid] < values[lo]) swap(values, mid, lo);
if (values[hi] < values[lo]) swap(values, hi, lo);
if (values[hi] < values[mid]) swap(values, hi, mid);
return values[mid];
}
/**
* @param {number[]} values
* @param {number} a
* @param {number} b
*/
function swap(values, a, b) {
[values[a], values[b]] = [values[b], values[a]];
}
# Quick sort, in place: Hoare partition around a median-of-three pivot.
# Pick a pivot, move the small values left and the big values right, then sort each side.
from typing import List
def quick_sort(values: List[int]) -> None:
"""Sort values in ascending order, in place.
Not stable: equal values may end up in a different order than they started.
"""
_sort_range(values, 0, len(values) - 1)
def _sort_range(values: List[int], lo: int, hi: int) -> None:
"""Sort values[lo..hi] (both ends included).
Recurse into the smaller side and loop on the bigger one, so the call
stack never grows past about log2(n) frames — even with unlucky pivots.
"""
while lo < hi:
split = _hoare_partition(values, lo, hi)
left_size = split - lo + 1
right_size = hi - split
if left_size < right_size:
_sort_range(values, lo, split) # small side: recursion
lo = split + 1 # big side: next turn of the loop
else:
_sort_range(values, split + 1, hi)
hi = split
def _hoare_partition(values: List[int], lo: int, hi: int) -> int:
"""Hoare partition of values[lo..hi].
Return split with lo <= split < hi such that every value in [lo, split]
is <= every value in [split + 1, hi]. Both sides are non-empty, so each
one is strictly smaller than the range we started with.
"""
pivot = _median_of_three(values, lo, hi)
i = lo - 1
j = hi + 1
while True:
# Walk i right past values that already belong on the left…
i += 1
while values[i] < pivot:
i += 1
# …and j left past values that already belong on the right.
j -= 1
while values[j] > pivot:
j -= 1
if i >= j:
return j # the two walks met: everything is on its side
values[i], values[j] = values[j], values[i] # both on the wrong side — trade places
def _median_of_three(values: List[int], lo: int, hi: int) -> int:
"""Put values[lo], values[mid], values[hi] in order and return the middle one.
On sorted or reversed input this picks the true median, which is exactly
where "always take the first element" falls to O(n²).
"""
mid = lo + (hi - lo) // 2
if values[mid] < values[lo]:
values[mid], values[lo] = values[lo], values[mid]
if values[hi] < values[lo]:
values[hi], values[lo] = values[lo], values[hi]
if values[hi] < values[mid]:
values[hi], values[mid] = values[mid], values[hi]
return values[mid]
/**
* Quick sort, in place: Hoare partition around a median-of-three pivot.
* Pick a pivot, move the small values left and the big values right, then sort each side.
*/
public final class QuickSort {
private QuickSort() {
}
/**
* Sorts values in ascending order, in place.
* Not stable: equal values may end up in a different order than they started.
*/
public static void quickSort(int[] values) {
sortRange(values, 0, values.length - 1);
}
/**
* Sorts values[lo..hi] (both ends included).
* Recurses into the smaller side and loops on the bigger one, so the call stack never grows
* past about log2(n) frames — even when the pivots are unlucky.
*/
private static void sortRange(int[] values, int lo, int hi) {
while (lo < hi) {
int split = hoarePartition(values, lo, hi);
int leftSize = split - lo + 1;
int rightSize = hi - split;
if (leftSize < rightSize) {
sortRange(values, lo, split); // small side: recursion
lo = split + 1; // big side: next turn of the loop
} else {
sortRange(values, split + 1, hi);
hi = split;
}
}
}
/**
* Hoare partition of values[lo..hi]. Returns split with lo <= split < hi such that
* every value in [lo, split] is <= every value in [split + 1, hi].
* Both sides are non-empty, so each one is strictly smaller than the range we started with.
*/
private static int hoarePartition(int[] values, int lo, int hi) {
int pivot = medianOfThree(values, lo, hi);
int i = lo - 1;
int j = hi + 1;
while (true) {
// Walk i right past values that already belong on the left…
do {
i++;
} while (values[i] < pivot);
// …and j left past values that already belong on the right.
do {
j--;
} while (values[j] > pivot);
if (i >= j) {
return j; // the two walks met: everything is on its side
}
swap(values, i, j); // both are on the wrong side — trade places
}
}
/**
* Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
* On sorted or reversed input this picks the true median, which is exactly where
* "always take the first element" falls to O(n²).
*/
private static int medianOfThree(int[] values, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (values[mid] < values[lo]) {
swap(values, mid, lo);
}
if (values[hi] < values[lo]) {
swap(values, hi, lo);
}
if (values[hi] < values[mid]) {
swap(values, hi, mid);
}
return values[mid];
}
private static void swap(int[] values, int a, int b) {
int tmp = values[a];
values[a] = values[b];
values[b] = tmp;
}
}
// Quick sort, in place: Hoare partition around a median-of-three pivot.
// Pick a pivot, move the small values left and the big values right, then sort each side.
// (In real code reach for std::sort — an introsort built on the same idea.)
#include <utility>
#include <vector>
// Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
// On sorted or reversed input this picks the true median, which is exactly where
// "always take the first element" falls to O(n²).
int medianOfThree(std::vector<int>& values, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (values[mid] < values[lo]) {
std::swap(values[mid], values[lo]);
}
if (values[hi] < values[lo]) {
std::swap(values[hi], values[lo]);
}
if (values[hi] < values[mid]) {
std::swap(values[hi], values[mid]);
}
return values[mid];
}
// Hoare partition of values[lo..hi]. Returns split with lo <= split < hi such that
// every value in [lo, split] is <= every value in [split + 1, hi].
// Both sides are non-empty, so each one is strictly smaller than the range we started with.
int hoarePartition(std::vector<int>& values, int lo, int hi) {
int pivot = medianOfThree(values, lo, hi);
int i = lo - 1;
int j = hi + 1;
while (true) {
// Walk i right past values that already belong on the left…
do {
++i;
} while (values[i] < pivot);
// …and j left past values that already belong on the right.
do {
--j;
} while (values[j] > pivot);
if (i >= j) {
return j; // the two walks met: everything is on its side
}
std::swap(values[i], values[j]); // both are on the wrong side — trade places
}
}
// Sorts values[lo..hi] (both ends included).
// Recurses into the smaller side and loops on the bigger one, so the call stack never grows
// past about log2(n) frames — even when the pivots are unlucky.
void sortRange(std::vector<int>& values, int lo, int hi) {
while (lo < hi) {
int split = hoarePartition(values, lo, hi);
int leftSize = split - lo + 1;
int rightSize = hi - split;
if (leftSize < rightSize) {
sortRange(values, lo, split); // small side: recursion
lo = split + 1; // big side: next turn of the loop
} else {
sortRange(values, split + 1, hi);
hi = split;
}
}
}
// Sorts values in ascending order, in place.
// Not stable: equal values may end up in a different order than they started.
void quickSort(std::vector<int>& values) {
sortRange(values, 0, static_cast<int>(values.size()) - 1);
}
Ask about this algorithm
Stuck on a step? Ask for another example or why it works.
Test yourself
10 quick questions to check it stuck.
Q1 · This quick sort picks its pivot as the median of three. Which value is the pivot for [7, 2, 9, 4, 3, 8, 1]?
Take it further
- Animation
Quick Sort Animation
Quick sort, step by step: the pivot, Hoare's two pointers and a call stack that stays shallow
Free
