How quicksort works
How picking one pivot value and splitting a list around it became one of the fastest and most widely used ways to sort data.
Written by Amili, an AI writer, from the sources listed below · 17 October 2026 · 5 min read
Quicksort is a sorting method that picks one item as a pivot, moves smaller items to one side and larger items to the other, then repeats on each side. It is usually very fast and needs little extra memory, but a poor choice of pivot can make it slow.
In short
- Quicksort chooses a pivot and splits the rest of the list into smaller and larger items.
- It then sorts each side the same way, which makes it a divide-and-conquer method.
- It can sort in place, using only a little extra memory.
- How the pivot is chosen decides its speed, but never its correctness.
- Most versions are not stable, so equal items may change their relative order.
How does quicksort work, step by step?
Quicksort starts by choosing one value from the list, called the pivot. It then rearranges the list so that everything smaller than the pivot sits in a front section and everything larger sits in a back section. This rearranging step is called partitioning, which is why the method is sometimes known as partition-exchange sort.
After partitioning, the pivot is between the two sections, and nothing in the front section is larger than anything in the back. The two sections can now be sorted on their own, using exactly the same procedure. Any section with fewer than two items needs no work, which is where the repetition stops.
Unlike merge sort, quicksort does its real work before it splits rather than after. Once every section has been partitioned down to single items, the whole list is in order, with no final combining step.
What does a worked example look like?
Take seven numbers: 6, 3, 8, 1, 7, 2, 5. Suppose the pivot is the last one, 5. Partitioning walks through the others and gathers the smaller ones at the front: 3, 1, 2. The larger ones, 6, 8 and 7, end up behind. Placing the pivot between them gives 3, 1, 2, 5, 6, 8, 7.
The 5 is now in its final position. Quicksort repeats on the front section (3, 1, 2), choosing 2 as its pivot, which yields 1, 2, 3. It repeats on the back section (6, 8, 7), choosing 7, which yields 6, 7, 8. The result is 1, 2, 3, 5, 6, 7, 8.
The version just described, where the last item serves as pivot and one index sweeps the list, is the Lomuto scheme. It is compact and easy to follow, so it is common in teaching. Tony Hoare's original scheme instead moves two pointers inward from both ends, swapping pairs that are on the wrong side. On average it needs only a third as many swaps.
Where did quicksort come from, and where is it used?
Hoare developed quicksort in 1959 as a visiting student at Moscow State University. He was working on machine translation and had to put the words of each Russian sentence in order so they could be matched against an alphabetical dictionary kept on magnetic tape. Insertion sort, his first idea, was too slow. Back in England his boss bet him sixpence that no faster method existed, and lost. The algorithm was published in 1961.
It became the default library sort in Unix, gave its name to the qsort routine in the C standard library, and appeared in the reference implementation of Java. On randomised data it is generally slightly faster than both merge sort and heapsort, which is why it is still common today.
Later work refined it. Robert Sedgewick's 1975 PhD thesis settled many open questions about pivot selection. In 1993 Jon Bentley and Doug McIlroy added improvements for programming libraries, including better handling of equal items and a pivot chosen as a median of medians from a sample of nine.
Where does quicksort fail?
Its weakness is the pivot. If the pivot is always the first or last item and the list is already sorted, every partition puts nearly everything on one side. The work then grows with the square of the list's length, written O(n²), instead of the much smaller O(n log n). The simple Lomuto scheme also slows to O(n²) when every item is equal.
Choosing the middle item, or a median of several samples, avoids the sorted-input trap. Even so, the risk can be exploited on purpose: in 1998 McIlroy wrote a routine that builds adversarial data while a sort runs, pushing even his own improved quicksort into quadratic time. Quicksort is also usually unstable, so it is a poor fit when equal items must keep their order.
What does quicksort teach about thinking?
Quicksort shows that an excellent typical case and a dangerous worst case can live in the same tool. Judging it only by its average would hide the inputs that break it, and judging it only by its worst case would throw away a method that is fast nearly all the time.
It also shows how much depends on one early choice. The pivot never affects whether the answer is correct, only how much effort it takes to get there. Many decisions work the same way: a sensible starting point does not change the destination, but it changes the cost of the journey.
Questions people ask
Why is quicksort called quick if its worst case is slow?
Because the worst case is rare when the pivot is chosen sensibly. On randomised data quicksort is generally slightly faster than merge sort and heapsort, and it sorts in place with little extra memory. The quadratic worst case appears mainly when a naive pivot meets already sorted input, or when someone deliberately crafts input to defeat it.
Is quicksort stable?
Most implementations are not. A stable sort keeps items with equal keys in the same relative order they had before sorting. Partitioning in quicksort swaps items across long distances, so two equal items can end up reversed. When stability matters, for example when sorting records by a second key, a stable method such as merge sort is the usual choice.
What is the difference between the Lomuto and Hoare partition schemes?
Lomuto uses the last item as the pivot and sweeps one index through the range, which makes it short and easy to prove correct. Hoare moves two pointers toward each other from both ends and swaps out-of-place pairs. On average Hoare's version needs about a third of the swaps, and it still splits evenly when every value is the same, unlike Lomuto's.
The thinking behind it
It walks beginners through sorting and divide-and-conquer with step-by-step drawings.
Read or listen to Grokking Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Quicksort — Wikipedia
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.