Quick sort, explained

Quick sort is another divide and conquer algorithm. It picks one value as the pivot and rearranges the list so that everything smaller is on its left and everything bigger is on its right.

The pivot is now in its final place. The same idea is then applied to the left and right parts.

How it works

• Choose a pivot value.
• Rearrange the list so smaller values come before the pivot and bigger values after it.
• The pivot is now in its correct final position.
• Repeat for the part on the left and the part on the right.

A small example

Sort this list, using 5 as the first pivot:

8 3 7 1 5

Partition:   [3 1]  5  [8 7]
Sort sides:  [1 3]  5  [7 8]
Result:      1 3 5 7 8

What to know about its cost

• Average and best case O(n log n).
• Worst case O(n²) when the pivots are badly chosen, for example on a list that is already sorted with a poor pivot rule.
• Sorts in place and uses O(log n) space for the recursion. It is not stable.

Where it works well

• Usually very fast in practice.
• Needs little extra memory.

Where it struggles

• Bad pivots can make it slow.
• Not stable.

Try it yourself

Open the Sorting experiment, enter the list 8 3 7 1 5, choose Quick Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment