- Hybrid sorting algorithms: intro sort, Tim sort
- Ideal sorting algorithm features: stable, in-place, adaptive
Comparison Sorting Algorithm Complexity
| Algorithm | Best Time | Average Time | Worst Time | 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 |
| Intro sort | Ω(n⋅log n) | Θ(n⋅log n) | O(n⋅log n) | O(log n) | in-place, hybrid |
| Tim sort | Ω(n) | Θ(n⋅log n) | O(n⋅log n) | O(n) | stable, adaptive, hybrid |
Integer Sorting Algorithm Complexity
| Algorithm | Best Time | Average Time | Worst Time | Space |
|---|---|---|---|---|
| Counting sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Bucket sort | Ω(n+k) | Θ(n+k) | O(n2) | O(n) |
| Radix sort | Ω(n⋅k) | Θ(n⋅k) | O(n⋅k) | O(n+k) |
- Read BetterExplained's sorting algorithms article that discusses similarities, differences, and patterns
- Play with VisuAlgo's interactive sorting visualizations including bubble, selection, insertion, merge, quick, counting, and radix sort
- Play with USF's interactive sorting animations including bubble, selection, insertion, merge, quick, Shell, sort
- Read Vaidehi Joshi's overview of sorting article with beautiful drawings and excellent analysis
- Play with Carlo Zapponi's sorting visualizations artwork including three-way quick sort
- Review Eric Rowell's Big O cheat sheet for a comparison of sorting algorithm time and space complexity
- Watch Toptal's sorting animations to compare algorithms based on input conditions (order and distribution)
- Read the discussion section on properties of an ideal sorting algorithm and the conclusion stated
- Watch Morolin's sorting algorithms visualized and compared with animated rainbow GIF loops
- Play with Casper Beyer's Tone of Sorting sound auralizer and read his article about how and why he built it
- Watch dancers perform sorting algorithms with folk dances including bubble sort, selection sort, insertion sort, Shell sort, merge sort, and quick sort
- Watch videos to observe patterns: 9 sorting algorithms, 15 sorting algorithms, 23 sorting algorithms
- 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
- Read Tim Peters's (a Python core language developer) proposal for a new sorting algorithm now known as Tim sort – he effectively argued its advantages over the existing sorting algorithm and compared performance with benchmarks
- Sorting algorithms project with real-world data on Make School's Online Academy