Quick Sort
Pick one value as the pivot and push everything smaller to its left. The pivot is then home for good, and the two sides are smaller versions of the same problem.
Sort 7 values. Each round picks a pivot and moves everything smaller to its left.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.
5 against the pivot 7. What happens?
Answer: Swap it left. 5 < 7, so it joins the smaller group at the boundary.
1 against the pivot 7. What happens?
Answer: Swap it left. 1 < 7, so it joins the smaller group at the boundary.
4 against the pivot 7. What happens?
Answer: Swap it left. 4 < 7, so it joins the smaller group at the boundary.
2 against the pivot 7. What happens?
Answer: Swap it left. 2 < 7, so it joins the smaller group at the boundary.
8 against the pivot 7. What happens?
Answer: Leave it. 8 >= 7, so the boundary does not move.
3 against the pivot 7. What happens?
Answer: Swap it left. 3 < 7, so it joins the smaller group at the boundary.
5 against the pivot 3. What happens?
Answer: Leave it. 5 >= 3, so the boundary does not move.
1 against the pivot 3. What happens?
Answer: Swap it left. 1 < 3, so it joins the smaller group at the boundary.
4 against the pivot 3. What happens?
Answer: Leave it. 4 >= 3, so the boundary does not move.
2 against the pivot 3. What happens?
Answer: Swap it left. 2 < 3, so it joins the smaller group at the boundary.
1 against the pivot 2. What happens?
Answer: Swap it left. 1 < 2, so it joins the smaller group at the boundary.
5 against the pivot 4. What happens?
Answer: Leave it. 5 >= 4, so the boundary does not move.
How it runs, step by step
Sort 7 values. Each round picks a pivot and moves everything smaller to its left.
Quick sort on 5, 1, 4, 2, 8, 3, 7. Each round partitions a range around a pivot, then sorts the two sides.
Work on indices 0 to 6. Take the last value, 7, as the pivot.
Partitioning indices 0 to 6. The pivot is 7 at index 6. The boundary i starts at index 0.
5 is smaller than the pivot 7, so it belongs on the left.
Comparing 5 at index 0 with the pivot 7. It is smaller, so it moves to index 0 and the boundary grows to 1.
1 is smaller than the pivot 7, so it belongs on the left.
Comparing 1 at index 1 with the pivot 7. It is smaller, so it moves to index 1 and the boundary grows to 2.
4 is smaller than the pivot 7, so it belongs on the left.
Comparing 4 at index 2 with the pivot 7. It is smaller, so it moves to index 2 and the boundary grows to 3.
2 is smaller than the pivot 7, so it belongs on the left.
Comparing 2 at index 3 with the pivot 7. It is smaller, so it moves to index 3 and the boundary grows to 4.
8 is not smaller than the pivot 7, so it stays where it is.
Comparing 8 at index 4 with the pivot 7. It is not smaller, so it stays in the right-hand group.
3 is smaller than the pivot 7, so it belongs on the left.
Comparing 3 at index 5 with the pivot 7. It is smaller, so it moves to index 4 and the boundary grows to 5.
Swap the pivot 7 with 8 so it lands between the two groups.
The pivot 7 moves to index 5. Everything to its left is smaller and everything to its right is not.
Index 5 is finished. The pivot never has to move again.
Index 5 is in its final position and will not be touched again.
A range of one value is already sorted, so index 6 is done.
Index 6 holds a single value, which is already in place.
Work on indices 0 to 4. Take the last value, 3, as the pivot.
Partitioning indices 0 to 4. The pivot is 3 at index 4. The boundary i starts at index 0.
5 is not smaller than the pivot 3, so it stays where it is.
Comparing 5 at index 0 with the pivot 3. It is not smaller, so it stays in the right-hand group.
1 is smaller than the pivot 3, so it belongs on the left.
Comparing 1 at index 1 with the pivot 3. It is smaller, so it moves to index 0 and the boundary grows to 1.
4 is not smaller than the pivot 3, so it stays where it is.
Comparing 4 at index 2 with the pivot 3. It is not smaller, so it stays in the right-hand group.
2 is smaller than the pivot 3, so it belongs on the left.
Comparing 2 at index 3 with the pivot 3. It is smaller, so it moves to index 1 and the boundary grows to 2.
Swap the pivot 3 with 4 so it lands between the two groups.
The pivot 3 moves to index 2. Everything to its left is smaller and everything to its right is not.
Index 2 is finished. The pivot never has to move again.
Index 2 is in its final position and will not be touched again.
Work on indices 0 to 1. Take the last value, 2, as the pivot.
Partitioning indices 0 to 1. The pivot is 2 at index 1. The boundary i starts at index 0.
1 is smaller than the pivot 2, so it belongs on the left.
Comparing 1 at index 0 with the pivot 2. It is smaller, so it moves to index 0 and the boundary grows to 1.
The pivot 2 is already past every smaller value, so index 1 is its home.
The pivot 2 moves to index 1. Everything to its left is smaller and everything to its right is not.
Index 1 is finished. The pivot never has to move again.
Index 1 is in its final position and will not be touched again.
A range of one value is already sorted, so index 0 is done.
Index 0 holds a single value, which is already in place.
Work on indices 3 to 4. Take the last value, 4, as the pivot.
Partitioning indices 3 to 4. The pivot is 4 at index 4. The boundary i starts at index 3.
5 is not smaller than the pivot 4, so it stays where it is.
Comparing 5 at index 3 with the pivot 4. It is not smaller, so it stays in the right-hand group.
Swap the pivot 4 with 5 so it lands between the two groups.
The pivot 4 moves to index 3. Everything to its left is smaller and everything to its right is not.
Index 3 is finished. The pivot never has to move again.
Index 3 is in its final position and will not be touched again.
A range of one value is already sorted, so index 4 is done.
Index 4 holds a single value, which is already in place.
Sorted. 12 comparisons and 6 swaps.
Result: the array is sorted in ascending order after 12 comparisons and 6 swaps.
Write it yourself
Define quickSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 6 examples.
// Partition around a pivot so smaller values sit left and larger right, then sort each side.function quickSort(values) { return values;}
Remember
- Every pivot that lands is finished, which is why no final pass is needed.
- O(n log n) on average, but O(n^2) when the pivot is always the smallest or largest.
- Sorting an already sorted array is the worst case for a last-value pivot.
Topics covered
Related
Where this is used
DatabasesPostgreSQL sorting rows that fit in memory
When an ORDER BY or a sort-merge join has fewer rows than work_mem allows, PostgreSQL quicksorts them in place and EXPLAIN ANALYZE prints the line Sort Method: quicksort. In place is the point: every backend shares the memory budget, so a sort that needs a second array of the same size would halve how much can be sorted before the plan has to spill to disk and switch to external merge sort.
Language runtimesJava's Arrays.sort on primitives
Sorting an int[] runs dual-pivot quicksort, which picks two pivots and splits into three regions per pass, while sorting objects runs Timsort instead. The split is about stability: Java guarantees equal objects keep their original order, and quicksort cannot promise that because partitioning swaps elements across the array. Two equal ints are indistinguishable, so instability costs nothing there and the sort gets to skip the side buffer Timsort has to allocate to merge runs.
Standard librariesstd::sort and introsort
The C++ standard requires O(n log n) worst case, which plain quicksort cannot promise, so implementations run introsort: quicksort while the recursion stays shallower than about 2 * log2(n), and heapsort on any subrange that goes deeper. Recursion also stops early on subranges of roughly sixteen elements, which a single insertion sort pass at the end cleans up, because insertion sort is faster than partitioning once a range is nearly in order. The depth counter is the whole trick, turning the n^2 case into a fallback that fires rarely and costs a constant factor when it does.
Scientific computingMedians and percentiles without sorting
NumPy's np.partition and np.median use introselect, which is quicksort's partition step with one half of the recursion deleted: after a partition you know the pivot's final rank, so you only descend into the side that contains the rank you want. Halving the remaining work instead of doing both sides makes selection linear on average rather than n log n, which is how a p99 latency figure is pulled from a large sample cheaply.
Why it works this way
How to stop the sorted-input worst case
The fix is one line before partitioning: swap a randomly chosen index, or the median of the first, middle and last values, into hi and leave the rest of the code alone. Median-of-three is the cheaper of the two and it directly covers sorted and reverse-sorted input, which is the shape real data actually arrives in. Randomising buys something extra: with a fixed rule, anyone who knows it can hand you input built to hit the quadratic case on purpose, which is a real denial-of-service route against a server that sorts what users send it.
An array of equal values is the other worst case
The test is a[j] < pivot, so a value equal to the pivot never moves left. Feed in an array where every value is the same and each partition drops the pivot at lo with n - 1 elements still on the right, which is the n^2 case again with no bad luck involved. Switching to <= does not fix it, it only moves the pile to the other side. The real fix is a three-way partition, the Dutch national flag: grow a middle band of values equal to the pivot and recurse only on the strictly smaller and strictly larger sides, which turns an all-duplicates array into a single linear pass.
Both recursive calls have to skip index i
After swap(a, i, hi) the pivot sits at i and is finished, so i is the one index neither call may include. Writing quickSort(a, lo, i) instead of i - 1 lets a two-element range hand itself the same range again and recurse until the stack dies. It is the same mistake as writing low = mid in binary search: the range has to get strictly smaller every time, and the element you just placed is what makes it shrink.
Where the O(log n) space goes
Nothing is allocated, so the space is purely the recursion stack: one frame per level of nesting. Levels are log n only while the partitions are roughly even, and the same bad pivots that cause the n^2 time also push the depth to n, so a large array can overflow the stack before it finishes sorting. Library implementations cap it by recursing into the smaller side and looping on the larger one instead of calling it, which holds the depth at log n no matter how badly the pivots fall.
Read more
- QuicksortWikipedia
- Dutch national flag problemWikipedia
- IntrosortWikipedia
- Engineering a sort functionBentley and McIlroy, 1993 · cs.fit.edu
- Finding the k-th order statistic in O(n)cp-algorithms