cf.completefrontend
SORTING · CORE

Quick sort

Pick one item as a pivot, move smaller items before it and the rest after it, then sort each side the same way.

Time O(n log n) on averageSpace O(log n) on average5 practice problemsStep-through picture

The idea

Quick sort picks one item, called the pivot, and rearranges the list so that every item smaller than the pivot comes before it and every other item comes after it. This step is called partitioning. After it, the pivot is in its final sorted position.

Then quick sort does the same thing to the part before the pivot and the part after it, separately. Each part gets its own pivot, and so on, until the parts are one item or empty.

On average quick sort is O(n log n) and very fast in practice, because it sorts in place and walks memory in order. Its weak spot is the pivot choice: if the pivot is always the smallest or largest item, as with the last item of an already sorted list, it slows down to O(n²).

An everyday example

Splitting a class around one student's height

A coach wants a line of players sorted by height. She picks one player and says: "Everyone shorter than her, stand on the left. Everyone else, stand on the right." Now that player is exactly where she belongs. The coach then does the same thing with the left group and with the right group, each with its own chosen player, until every group is one person.

How the example maps to the code
In the exampleIn the code
The chosen playerpivot = items[high]
"Shorter than her, stand on the left"if (items[j] < pivot) swap into the store area
The edge of the left groupstore
The chosen player stepping into the gapThe final swap: items[store] and items[high]
Repeating with each groupquickSort(items, low, p - 1) and quickSort(items, p + 1, high)

From the slow way to quick sort

  1. Merge sort splits the list at the middle without looking at the values, then does all the real work while merging, in a new array. Can we do the work before splitting instead, and inside the same array? We could if we split by value: small items on one side, big items on the other.
  2. Pick any item and call it the pivot. Move every item smaller than the pivot to the left, everything else to the right, and put the pivot between them. Now the pivot is exactly where it belongs in the sorted list, and no item ever has to cross it. The two sides can be sorted separately, and there is nothing to merge afterwards.
  3. Splitting by value can be done in one pass, in place. Walk j across the range and keep a boundary store: everything before store is smaller than the pivot. When items[j] is smaller, swap it to store and move the boundary one step right. At the end, swap the pivot into store. This pass is called partitioning, and it costs O(n).
  4. If the pivot lands near the middle, each side has about half the items, and we get the same log n levels as merge sort. If it lands at an end, one side is empty and we only peeled off one item. So the speed depends entirely on the pivot. Partition around a pivot, then sort the two sides the same way: that recursion is quick sort.

How it works

  1. If the range low..high has fewer than two items, it is sorted: stop.
  2. Choose the pivot. This template uses the last item, pivot = items[high].
  3. Partition: walk j from low to high - 1. Keep store as the place for the next small item. When items[j] < pivot, swap it into items[store] and add 1 to store.
  4. Swap the pivot from high into store. Now everything left of store is smaller and everything right of it is not.
  5. Quick sort the part low..store - 1 and the part store + 1..high.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function quickSort(items, low = 0, high = items.length - 1) {
  2. if (low >= high) return items;
  3. const p = partition(items, low, high);
  4. quickSort(items, low, p - 1);
  5. quickSort(items, p + 1, high);
  6. return items;
  7. }
  9. function partition(items, low, high) {
  10. const pivot = items[high];
  11. let store = low;
  12. for (let j = low; j < high; j++) {
  13. if (items[j] < pivot) {
  14. [items[store], items[j]] = [items[j], items[store]];
  15. store++;
  16. }
  17. }
  18. [items[store], items[high]] = [items[high], items[store]];
  19. return store;
  20. }

How fast it is

TimeO(n log n) on average
Extra memoryO(log n) on average

Each level of recursion partitions all items once, O(n). Good pivots give about log n levels; bad ones give n. The memory is the recursion stack, one frame per level.

  • Best caseO(n log n)

    Every pivot lands in the middle of its range, so each level halves the work, as with pivots 4, 2, and 6 in [1, 3, 2, 6, 5, 7, 4].

  • Average caseO(n log n)

    A random order (or random pivots). About 1.39 × n × log₂ n comparisons on average, with a small constant and in-place swaps, which is why it is fast in practice.

  • Worst caseO(n²)

    Every pivot is the smallest or largest item: with the last item as pivot, that is an already sorted list, a reversed list, or all-equal values like [7, 7, 7, 7]. 1,000 equal items cost 499,500 comparisons.

Common mistakes

  • Always using the last (or first) item as the pivot on data that may already be sorted. It becomes O(n²) and can hit "Maximum call stack size exceeded". Pick a random pivot.
  • Recursing on low..p and p..high, including the pivot. The range may never shrink, and the recursion never ends.
  • Expecting a stable sort. Partition swaps items over long distances, so equal items can change order.
  • Using it on lists with many repeated values without a three-way partition. Every item equal to the pivot lands on one side, which can make it O(n²).

When to use it

Look for these clues in a problem:

  • You need a fast in-place sort and do not need equal items to keep their order.
  • The question is about partitioning: putting items smaller than some value first.
  • You need only one position of the sorted order (like the median or the k-th largest): the partition step alone, repeated on one side, does it (quickselect).

Check yourself

Answer each one in your head first, then open it.

Why must the recursive calls use p - 1 and p + 1, not p?

The pivot is already in its final place. Including it keeps a range the same size in the worst case, so the recursion may never shrink and never end.

How many comparisons does partition make on a range of 8 items?

Seven: j walks from low to high - 1, comparing each item with the pivot once. The pivot itself is not compared.

Why is quick sort usually faster than heap sort, when both are O(n log n) on average?

Partition walks memory in order and does simple swaps, which modern CPUs handle very fast. Heap sort jumps between parents and children far apart in the array, which wastes the cache.

What happens to the recursion depth on a reversed list of 6 items?

Each call peels off just one item, so the calls nest about 6 deep instead of about log₂ 6, which is under 3. On large lists that depth overflows the stack.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Partition keeps a rule at the top of each loop step: every item in items[low..store-1] is smaller than the pivot, and every item in items[store..j-1] is not. At the start both parts are empty. When items[j] is smaller, swapping it with items[store] and adding 1 to store grows the first part by one, and the item it swapped out simply moves to the end of the second part. When it is not smaller, j moves on and the second part grows.

When the walk ends, j has reached high, so the rule covers the whole range except the pivot. Swapping the pivot into store gives a range where everything left of store is smaller and everything right of it is not. In the sorted list, exactly store - low items of this range come before the pivot, so store is the pivot's final position.

The recursion is correct by induction. A range with fewer than two items is sorted. A longer range is partitioned, and the two sides low..p-1 and p+1..high are strictly smaller, because the pivot is left out of both. Sorting each side never moves an item across the pivot, so after both calls the whole range is sorted.

Going deeper

3 more ideas

Why partitioning puts the pivot in its final place

During the walk, items[low..store-1] holds only items smaller than the pivot, and items[store..j-1] holds only items that are not smaller. Each step keeps this true. At the end, the pivot moves to store, with exactly the smaller items before it. However the two sides are sorted later, they stay on their side, so the pivot never moves again.

Average and worst case

If the pivot usually lands near the middle, each level of recursion halves the parts, giving about log n levels of O(n) partitioning: O(n log n). If the pivot is always the smallest or largest item, one side is empty and the other has n - 1 items, giving n levels: O(n²), and recursion that deep can overflow the call stack. With the last item as pivot, an already sorted list is exactly this bad case.

Choosing better pivots

Picking a random index as the pivot (swap it to high first) makes the bad case extremely unlikely for any input. Another common trick is the median of three: use the middle value of the first, middle, and last items. Lists with many equal values do better with a three-way partition that groups items smaller than, equal to, and bigger than the pivot.

Work it by hand

Every step in a table, with why

Sort 7 numbers using the last item as the pivot. The first partition is shown step by step, then each later partition in one row.

items = [3, 9, 4, 7, 1, 8, 5]

Steplow..highjitems[j]storeitemsWhat happensWhy
10..6031[3, 9, 4, 7, 1, 8, 5]3 < 5: swap, store++The pivot is items[6] = 5. store and j are both 0, so the swap exchanges 3 with itself.
20..6191[3, 9, 4, 7, 1, 8, 5]9 is not smaller: skip9 stays. It is now the first item of the "not smaller" group.
30..6242[3, 4, 9, 7, 1, 8, 5]4 < 5: swap with items[1]4 moves to the boundary, and 9 moves to where 4 was.
40..6372[3, 4, 9, 7, 1, 8, 5]7 is not smaller: skipThe "not smaller" group is now 9, 7.
50..6413[3, 4, 1, 7, 9, 8, 5]1 < 5: swap with items[2]1 jumps over 9 and 7, and 9 goes to index 4. Long jumps like this are why quick sort isn't stable.
60..6583[3, 4, 1, 7, 9, 8, 5]8 is not smaller: skipThe walk ends at j = 5, just before the pivot.
70..6--3[3, 4, 1, 5, 9, 8, 7]Pivot to store: p = 3Swap items[3] and items[6]. 5 is final; sort 0..2 and 4..6.
80..2--0[1, 4, 3, 5, 9, 8, 7]Pivot 1: p = 0Nothing is smaller than 1, so it swaps into index 0. The left side 0..-1 is empty.
91..2--1[1, 3, 4, 5, 9, 8, 7]Pivot 3: p = 14 is not smaller, so 3 swaps into index 1. Both sides have at most one item.
104..6--4[1, 3, 4, 5, 7, 8, 9]Pivot 7: p = 49 and 8 are both bigger. A bad split: the left side is empty, the right side has 2 items.
115..6--6[1, 3, 4, 5, 7, 8, 9]Pivot 9: p = 68 < 9, so store ends at 6 and the pivot swaps with itself. Every call left is a base case.

It returns [1, 3, 4, 5, 7, 8, 9] after 5 partitions and 12 comparisons. Six more calls, such as quickSort(items, 0, -1) and quickSort(items, 2, 2), stop at once because low >= high.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Quick sortO(n log n)O(log n)Sorting numbers in place where stability doesn't matter. With random pivots it is usually the fastest general sort.
Merge sortO(n log n)O(n)You need stability or a guaranteed worst case, and can afford O(n) extra memory.
Heap sortO(n log n)O(1)You need a guaranteed O(n log n) with constant extra memory, and can accept slower average speed.
QuickselectO(n)O(1)You only need one position of the sorted order, like the median. It partitions like quick sort but recurses into one side only.

Extra memory: O(log n) on average for the recursion stack, and O(n) in the worst case. In Node.js, the code above throws "Maximum call stack size exceeded" on an already sorted list of 10,000 items.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Quick sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Quick sort, Merge sort, Heap sort O(n log n)
  • Quickselect O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Quick sort339,96620 million
Merge sort339,96620 million
Heap sort339,96620 million
Quickselect101,0001 million

Inputs that need care

5 tricky inputs
An empty list or one item
high starts at -1 or 0, so low >= high returns at once.
Already sorted: [1, 2, 3, 4, 5]
Each pivot is the biggest in its range, so p = high every time and the left side holds everything else. That is n levels and O(n²) time. Swap a random item into high before partitioning to fix it.
All equal: [7, 7, 7, 7]
items[j] < pivot is never true, so store stays at low and each call removes only the pivot. Use a three-way partition that groups equal items in the middle and skips them.
Two items: [9, 2]
Pivot 2; 9 is not smaller, so store = 0 and the pivot swaps to index 0. Both sides are empty. The answer is [2, 9].
Equal items that must keep their order, like rows of a table
Quick sort can't promise that: partition swaps items across long distances. Use merge sort or the built-in stable sort.

Variations and follow-ups

Twists interviewers add

Random pivot

Before partitioning, swap a random item of low..high into high. No fixed input can now force the bad case, and the expected time is O(n log n) for every input. It is the simplest fix and the one to mention first.

Three-way partition

Split the range into smaller than, equal to, and bigger than the pivot, using three pointers, then recurse only on the outer two. Lists with many repeats, like ratings from 1 to 5, become fast instead of O(n²).

Hoare partition

Move one pointer from the left and one from the right, and swap pairs that are on the wrong side. It makes about three times fewer swaps than the version above on average, but the pivot does not end at a fixed index, so the recursion bounds change.

Introsort

Run quick sort, but count the recursion depth. If it passes about 2 × log₂ n, switch to heap sort for that range, and use insertion sort for tiny ranges. This keeps quick sort's speed with an O(n log n) guarantee; common C++ standard libraries sort this way.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the problem says "in place", "partition", "k-th smallest", or "all items less than x before the rest". The partition step is often the whole question.
  • Say the partition rule out loud: "everything before store is smaller than the pivot, everything from store to j is not". It makes each line of the loop easy to justify.
  • Test by hand with a sorted list (the bad case), a list of equal items, and a two-item list. Off-by-one bugs in p - 1 and p + 1 show up quickly in those.
  • The usual follow-up is "what is the worst case and how do you avoid it?". Answer: O(n²) when pivots are always extreme; use a random pivot, and a three-way partition for many repeats. Mention that recursing into the smaller side first keeps the stack at O(log n) even in bad cases.

Where frontend code uses it

The same idea in real UI code
  • Before 2018, V8 sorted arrays with quick sort (and insertion sort for short arrays), which is why sort used to be unstable in Chrome. V8 7.0 switched to TimSort.
  • Partitioning without a full sort shows up in UI code, such as moving all pinned items before unpinned ones, or all errors before warnings.
  • Quickselect, the one-sided version, finds medians and percentiles for performance dashboards without sorting the whole data set.

Related algorithms