Topics:
- hybrid sorting algorithms: introsort, Timsort
- ideal sorting algorithm features: stable, adaptive, in-place
Comparison Sorting Algorithm Complexity
| Algorithm | Best Time | Average Time | Worst Time | Worst Space | Features |
|---|---|---|---|---|---|
| Bubble sort | Ω(n) | Θ(n2) | O(n2) | O(1) | stable, in-place, adaptive |
| Selection sort | Ω(n2) | Θ(n2) | O(n2) | O(1) | stable, in-place |
| Insertion sort | Ω(n) | Θ(n2) | O(n2) | O(1) | stable, in-place, adaptive |
| Tree sort | Ω(n log(n)) | Θ(n log(n)) | O(n2) | O(n) | |
| Quick sort | Ω(n log(n)) | Θ(n log(n)) | O(n2) | O(log(n)) | in-place |
| Merge sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) | stable |
| Heap sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | in-place |
| Introsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(log(n)) | hybrid, in-place |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | hybrid, stable, adaptive |
Integer Sorting Algorithm Complexity
| Algorithm | Best Time | Average Time | Worst Time | Worst Space |
|---|---|---|---|---|
| Counting sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Bucket sort | Ω(n+k) | Θ(n+k) | O(n2) | O(n) |
| Radix sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
Resources:
- play with USF's interactive sorting animations to follow algorithms step-by-step
- watch Toptal's sorting animations to see how algorithms compare based on input data and read the discussion section
- watch TutorialsCC's sorting algorithm videos to observe patterns, especially the Timsort video
- watch people perform sorting algorithms with folk dances, especially merge sort with German folk dance and quick sort with Hungarian folk dance
- watch University of Toronto's "Sorting Out Sorting" 30-minute film from 1981
- download Timo Bingmann's The Sound of Sorting software to hear and visualize sorting algorithms
Project:
- sorting algorithms with real-world data on Make School's Online Academy