About this visualization
Quick sort picks a pivot, rearranges the list so smaller items are on its left and larger items on its right (partitioning), which places the pivot in its final position, then sorts each side. It is usually the fastest general-purpose comparison sort in practice.
How it works
- Choose the last item of the range as the pivot (Lomuto partition).
- Move every item smaller than the pivot to the left side.
- Place the pivot between the two sides, then recurse on each side.
Worked example
Sort [4, 2, 7, 1] with the last item as pivot. Pivot 1: nothing is smaller, so it swaps to the front → [1, 2, 7, 4] and is final. Sort [2, 7, 4] with pivot 4: 2 < 4 stays left, 7 does not, pivot swaps with 7 → [2, 4, 7]. The final list is [1, 2, 4, 7].
Enter these numbers in the simulator above to see every step.
Complexity and properties
| Best case | |
|---|---|
| Average case | |
| Worst case | |
| Space | |
| Stable | No |
| In-place | Yes |
Worst case happens on already sorted input with a last-item pivot; space is the recursion stack.
When to use it
- Understanding partitioning, the key idea behind many selection and sorting algorithms.
- Seeing why a bad pivot gives the worst case.
- Comparing quick sort with merge sort and heap sort.
Frequently asked questions
What is the time complexity of quick sort?
on average and in the best case, in the worst case (for example a sorted list with the last item as pivot). Space is for the recursion stack.
Is quick sort stable?
The standard in-place version is not stable.
How can the worst case be avoided?
Choose the pivot randomly or as the median of three items instead of always taking the last item.