Sorting, drawn the way the theory draws it
Pick an algorithm, set the number of elements and the speed, and watch the array being sorted. Every compare and swap is drawn as a mark in time, and the counters show exact comparisons, reads, writes and swaps, counted by the same rules for every algorithm. Turn on sound to hear each value as a frequency.
All algorithms
Exchange
| Algorithm | Average time | Worst time |
|---|---|---|
| Bubble Sort | Θ( n2 ) | O( n2 ) |
| Cocktail Shaker Sort | Θ( n2 ) | O( n2 ) |
| Comb Sort | Θ( n2 ) | O( n2 ) |
| Gnome Sort | Θ( n2 ) | O( n2 ) |
| Odd-Even Sort | Θ( n2 ) | O( n2 ) |
| Quick Sort | Θ( n log n ) | O( n2 ) |
| 3-Way Quick Sort | Θ( n log n ) | O( n2 ) |
| Dual-Pivot Quick Sort | Θ( n log n ) | O( n2 ) |
Selection
| Algorithm | Average time | Worst time |
|---|---|---|
| Selection Sort | Θ( n2 ) | O( n2 ) |
| Heap Sort | Θ( n log n ) | O( n log n ) |
| Cycle Sort | Θ( n2 ) | O( n2 ) |
| Pancake Sort | Θ( n2 ) | O( n2 ) |
Insertion
| Algorithm | Average time | Worst time |
|---|---|---|
| Insertion Sort | Θ( n2 ) | O( n2 ) |
| Shell Sort | Θ( n4/3 ) | O( n2 ) |
Merge
| Algorithm | Average time | Worst time |
|---|---|---|
| Merge Sort | Θ( n log n ) | O( n log n ) |
| Bitonic Sort | Θ( n log2 n ) | O( n log2 n ) |
Distribution
| Algorithm | Average time | Worst time |
|---|---|---|
| Counting Sort | Θ( n + k ) | O( n + k ) |
| Radix Sort | Θ( d(n + b) ) | O( d(n + b) ) |
| Bucket Sort | Θ( n + k ) | O( n2 ) |
Hybrid
| Algorithm | Average time | Worst time |
|---|---|---|
| Tim Sort | Θ( n log n ) | O( n log n ) |
| Intro Sort | Θ( n log n ) | O( n log n ) |
Novelty
| Algorithm | Average time | Worst time |
|---|---|---|
| Stooge Sort | Θ( n2.71 ) | O( n2.71 ) |
| Bogo Sort | Θ( n · n! ) | unbounded |