How Heapsort Works
- Waiting
- Being compared
- Just moved
- In final position
1/87
Heap sort, 12 values in random order.
Settings
More options
Starting order
Two to 48 numbers, used in the order you type them.
Heap Sort
- 1
for i in n/2-1 .. 0: - 2
siftDown(i, n) // build max-heap - 3
- 4
for end in n-1 .. 1: - 5
swap(0, end) // root is the max - 6
siftDown(0, end) - 7
- 8
siftDown: sink a value past its - 9
larger child until the heap holds
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.