Sorting Algorithms Overview: When to Use Which
Sorting is one of the most studied problems in computer science. Different algorithms trade off time, space, and stability. This post gives an overview of the most common ones and when to use them in practice.
Complexity at a glance
| Algorithm | Average | Worst | Space | Stable |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n²) | O(log n) | No* |
| Heapsort | O(n log n) | O(n log n) | O(1) | No |
*Quicksort can be made stable with extra space. In practice, language runtimes use tuned hybrids (e.g. Timsort).