- Part being partitioned
- Pivot
- Compared
- Swapped
- In place
Quicksort
Quicksort picks a pivot, moves every smaller value before it and every other value after it, and then sorts the two sides the same way. The pivot ends up in its final place after each partition. Choose how the pivot is picked, play the sort at any speed or step through it one comparison at a time, and see why a bad pivot on a sorted list makes quicksort slow. Press Play to watch the sort, or Step and Back to go one comparison at a time. Drag the step slider to jump anywhere. The tiles count comparisons, swaps and partitions. Choose how many bars, how they start, or type your own numbers, and how the pivot is chosen. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose how many bars and how they start: random, nearly sorted, reversed, or with few unique values. Or type your own numbers.
- Press Play, or use Step and Back to move one comparison at a time. Drag the step slider to jump anywhere in the sort.
- Pick the pivot rule: the last value, the middle value, a random value, or the median of three. Try each on a sorted list.
How quicksort works
Pick one value of the part to sort as the pivot and move it to the end. Walk through the other values from left to right; each one that is smaller than the pivot swaps into a left part that grows from the start. Then swap the pivot in right after the left part. Everything before it is now smaller and nothing after it is, so the pivot is in its final place. Sort the part before it and the part after it the same way, until every part is a single value.
Why the pivot matters
When the pivot lands near the middle, each partition halves the problem, and the comparisons grow like n log n: for 40 random values, about 190. When the pivot is the smallest or largest value, one side is empty and the other has everything else. With the last value as pivot that happens at every step on a sorted or reversed list, and the sort takes n(n − 1)/2 comparisons, 780 for 40 values. A random pivot or the median of the first, middle and last value avoids that in practice.
Frequently asked questions
How does quicksort work?
It picks a pivot, partitions the list so that the smaller values come before the pivot and the rest after it, and then sorts both sides with quicksort. After each partition the pivot is in its final place.
Why is quicksort slow on a sorted list?
With the first or last value as pivot, a sorted list always gives the smallest or largest value as pivot. One side of the partition is then empty, so each partition only removes one value, and the sort takes n(n − 1)/2 comparisons. A random pivot or the median of three fixes this in practice.
Is quicksort faster than merge sort?
Often, in practice: it sorts in place, needs no buffer, and its inner loop is very simple. On average it makes somewhat more comparisons than merge sort, and its worst case is n², while merge sort is always n log n. Library sorts such as introsort start with quicksort and switch to heap sort if the splits get too uneven.
Is quicksort stable?
No. A partition swaps values over long distances, so equal values can change order.
Are my numbers sent anywhere?
No. The sort runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor