Sorting Algorithm Comparison — Time, Space, and Stability
Compare all major sorting algorithms side by side: time complexity (best, average, worst), space complexity, stability, and when to use each one.
Detailed Explanation
Comprehensive Sorting Algorithm Comparison
Choosing the right sorting algorithm depends on the data size, whether the data is nearly sorted, memory constraints, and whether stability matters.
Complete Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable? | Adaptive? |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | No |
| Tim sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Yes |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | No |
| Radix sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | No |
| Bucket sort | O(n+k) | O(n+k) | O(n²) | O(n) | Yes | No |
When to Use Each
Small arrays (n < 50): Insertion sort. Low overhead, cache-friendly, and adaptive.
General purpose: Tim sort (default in Python and Java). It’s adaptive, stable, and O(n log n) worst case.
Memory constrained: Heap sort. In-place with guaranteed O(n log n).
Integers with small range: Counting sort or radix sort. They beat the O(n log n) comparison lower bound because they are not comparison-based.
Nearly sorted data: Insertion sort or Tim sort. Both are adaptive and will finish in near-linear time.
Need guaranteed O(n log n): Merge sort or heap sort. Quick sort’s worst case is O(n²), though randomized pivot selection makes this rare.
Stability
A stable sort preserves the relative order of equal elements. This matters when sorting by multiple keys (e.g., sort by name, then by age — stable sort preserves the name order for equal ages).
Parallelism
Merge sort is naturally parallelizable (sort two halves independently). Quick sort can be parallelized but load balancing depends on pivot quality.
Use Case
Sorting algorithm selection is a fundamental decision in software engineering. Use this comparison when choosing a sort for production code, preparing for interviews, or analyzing the performance characteristics of library sort implementations.
Try It — Big-O Reference
Related Topics
Linearithmic Time O(n log n) — The Optimal Sorting Boundary
Complexity Classes
Quadratic Time O(n²) — When Nested Loops Dominate
Complexity Classes
Best, Worst, and Average Case — Understanding Algorithm Bounds
Analysis Concepts
Space Complexity Basics — Understanding Memory Usage
Analysis Concepts
Constant Time O(1) — Operations That Never Slow Down
Complexity Classes