Interactive demo
Quicksort Visualization
Quicksort is a widely used sorting algorithm based on divide and conquer. It needs O(n log n) steps on average and O(n²) in the worst case.
Press “Next Step” to advance one step at a time, or “Play” to run the algorithm on its own. Try different starting orders below the buttons.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Unsorted element
- Pivot
- “lower” arrow
- “greater” arrow
- Final position
Runtime and properties
Best case
O(n log n)
Every pivot splits its section into two halves of equal size.
Average case
O(n log n)
Pivots split well enough on average: about log n levels with n comparisons each.
Worst case
O(n²)
The pivot is always the smallest or largest element, so each level only removes one element.
Extra memory
O(log n)
Only the recursion stack, as long as the smaller part is sorted first.
Stable
No
Swaps over long distances can change the order of equal elements.
In-place
Yes
Elements are only swapped within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort this page | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Pick a pivot
One element of the current section is chosen as the pivot and moved to the end of that section.
2. Partition
Two arrows walk toward each other and swap elements until everything smaller than the pivot is on the left and everything larger is on the right.
3. Recurse
The pivot moves to its final position and is marked as finished. The same steps then repeat for the left and the right part until the array is sorted.