Quicksort
Quicksort is one of the most used sorting algorithms. It picks a pivot, splits the list into the values smaller than the pivot and the rest, and sorts the two sides the same way. It is fast in practice and needs no extra list, but how fast depends on the pivot.
The idea
Choose one value as the pivot. Rearrange the list so that every value smaller than the pivot comes before it and every other value after it. That rearranging is called a partition, and it leaves the pivot exactly where it belongs in the sorted list. The two sides are now independent problems: sort each of them with quicksort. A side with one value or none is already sorted.
The partition, step by step
The app uses the Lomuto partition. The pivot is moved to the end of the part. A marker starts at the beginning: everything before it is smaller than the pivot. Each other value is compared with the pivot; if it is smaller, it swaps to the marker and the marker moves on one place. At the end, the pivot swaps to the marker. Take 5, 1, 4, 2, 8 with the last value as pivot: all four values are smaller than 8, so 8 stays at the end. The part 5, 1, 4, 2 is partitioned around 2, giving 1, 2, 4, 5, and 4, 5 around 5. That is 8 comparisons, 2 swaps and 3 partitions.
Good and bad pivots
If every pivot landed in the middle, each partition would halve the problem, and the sort would take about n log₂ n comparisons. On a random list the pivots are rarely perfect but usually good enough: for 40 random values the app counts about 190 comparisons. The worst case comes when the pivot is always the smallest or largest value. With the last value as pivot, a list that is already sorted, or reversed, does exactly that: every partition removes just the pivot, and the sort takes n(n − 1)/2 comparisons, 780 for 40 values.
Choosing the pivot
A random pivot makes the worst case extremely unlikely for any input, because no particular order can fool it. The median of three, the middle value of the first, middle and last element, is cheap and handles sorted and reversed lists well. Try both on a sorted list in the app and the comparisons drop from 780 to about 150. Many equal values are a different problem: they all land on one side of the pivot. A three-way partition, which keeps the values equal to the pivot in a middle part, fixes that.
History and use
Tony Hoare invented quicksort in 1959 and published it in 1961. His own partition scans from both ends and makes fewer swaps; the simpler Lomuto version shown here became popular through textbooks. Quicksort sorts in place and its inner loop is very short, so it is usually faster than merge sort in practice, though it is not stable. Introsort, the sort behind the C++ standard library, runs quicksort and switches to heap sort if the partitions become too uneven, so its worst case stays n log n.
Explore it
Open the app and press Step. The part being partitioned is shaded, the pivot has its own colour, and the dashed line marks the end of the left part, the values smaller than the pivot. Each pivot turns green when it reaches its final place. Choose a sorted list and the last value as pivot, then switch to the median of three, and compare the counters.
Frequently asked questions
What is the time complexity of quicksort?
O(n log n) on average and with good pivots, O(n²) in the worst case. It sorts in place; the recursion needs O(log n) extra memory when the smaller side is sorted first.
What is the difference between Lomuto and Hoare partitioning?
Lomuto keeps one marker and scans from left to right, which is easy to follow and is what this app shows. Hoare scans from both ends towards each other and swaps pairs that are on the wrong side, which makes about three times fewer swaps on average.
Why is quicksort slow when many values are equal?
Values equal to the pivot all go to the same side, so a list with few distinct values splits unevenly, and a list of equal values is as bad as the worst case. A three-way partition that collects the values equal to the pivot in the middle avoids that.
Is quicksort stable?
No. Swaps during a partition move values over long distances, so equal values can change their order.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try quicksort