The race
Every algorithm sorts the same 16 values. The clock counts work (comparisons, swaps and writes), not seconds, so the one that needs the fewest operations finishes first.
Array: 2, 7, 97, 70, 52, 41, 47, 24, 55, 73, 26, 16, 76, 52, 20, 37
key: empty, 7, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty
Array: 2, empty, 97, 70, 52, 41, 47, 24, 55, 73, 26, 16, 76, 52, 20, 37
Array: 2, 7, 97, 70, 52, 41, 47, 24, 55, 73, 26, 16, 76, 52, 20, 37
merge buffer B: empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty
Array: 2, 7, 97, 70, 52, 41, 47, 24, 55, 73, 26, 16, 76, 52, 20, 37
How the work grows
Comparisons + swaps + writes for random input as n goes from 4 to 64. The thin curves are n²/2 and n·log₂n for reference.
- Bubble Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- n²/2 (reference)
- n log₂ n (reference)
Bubble Sort makes about 2,900 operations. Quick Sort makes about 560.
Double n from 32 to 64 and bubble sort's work grows ×4.1; quick sort's grows ×2.5.