Sorting Algorithms
Seven sorting algorithms on the same array. Choose how many values and what order they start in, then play it through or step one comparison at a time.
- Waiting
- Being compared
- Just moved
- In final position
Speed
Step 1 of 102
Bubble sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
Algorithm
Starting order
Bubble sort
- 1
for i in 0..n-1: - 2
swapped = false - 3
for j in 0..n-i-2: - 4
if a[j] > a[j+1]: - 5
swap(j, j+1) - 6
swapped = true - 7
// a[n-1-i] is now final - 8
if not swapped: break
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 |
Stable means equal values keep their original order.