Sorting Algorithms
An overview of sorting — comparison-based vs non-comparison, stability, and how to choose the right algorithm for the job.
Sorting arranges elements into a defined order. It is a prerequisite for binary search, a building block for join algorithms in databases, and ubiquitous in ranked outputs.
Two Families
Comparison-based. Elements are ordered by comparing pairs — a < b? a == b? Any algorithm that can only determine order through comparisons has a lower bound of O(n log n). You cannot do better in the general case.
Non-comparison. Algorithms like counting sort, radix sort, and bucket sort exploit the structure of the keys themselves — their digit decomposition, their bounded range. They can sort in O(n) when their preconditions are met.
Stability
A sort is stable if equal elements maintain their original relative order. This matters when sorting by multiple keys: sort by last name first, then stably sort by first name — last names stay grouped correctly.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
The following articles cover each algorithm in depth — visual step traces, naive and optimized Rust implementations, and full complexity derivations.