How quicksort works
- Pick a pivot. This code takes the first value of the part being sorted.
- Move
iright from the left end while the values are smaller than the pivot. Movejleft from the right end while the values are greater. - If
ihas not passedj, swap the two values they stopped on and move both pointers one step inwards. - When
iandjhave crossed, nothing on the left is greater than the pivot and nothing on the right is smaller. Sort each side the same way.
What the colours mean
The dashed line marks the pivot value across the bars. Yellow is the value being compared with the pivot, and pink is a swap. Bars outside the part being sorted are faded. A bar turns green when its part is down to one value.
Quicksort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n²) | O(log n) on average | No |
With the first value as the pivot, a sorted array is the worst case: every partition splits off a single value, and the comparisons grow with the square of the size. Run Already sorted, then Random, at the same size and compare the counters. The article shows the one-line fix, a pivot taken from the middle.
The extra space is the call stack. It is about log n calls deep when the splits are even, and up to n deep in the worst case.
The C# code
The listing beside the bars is the SortArray() method from Quicksort Algorithm in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is quicksort stable?
No. The swaps move values across the pivot over long distances, so equal values can change order.
What is the worst case for quicksort?
Partitions that split off one value at a time. With the first value as the pivot that happens on sorted and reversed arrays, and the running time becomes O(n²).
Which pivot should quicksort use?
The first value is the simplest choice and the weakest on sorted data. The middle value handles sorted and reversed input well. Array.Sort in .NET goes further: it takes the median of three values and falls back to heap sort if the recursion gets too deep.