How Quicksort Works
- Waiting
- Being compared
- Just moved
- In final position
1/67
Quick sort, 12 values in random order.
Settings
More options
Starting order
Two to 48 numbers, used in the order you type them.
Quick Sort
- 1
stack = [(0, n-1)] - 2
while stack not empty: - 3
(lo, hi) = stack.pop() - 4
pivot = a[hi] - 5
i = lo - 6
for j in lo..hi-1: - 7
if a[j] <= pivot: - 8
swap(i, j); i += 1 - 9
swap(i, hi) // pivot final - 10
push (lo, i-1) and (i+1, hi)
How the Seven Compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Scroll the table sideways for the rest of the columns.
Stable means equal values keep their original order.