Comparison of All Sorting Algorithms — Complete Reference
Side-by-side comparison of 8 sorting algorithms: time complexity, space complexity, stability, adaptivity, and practical use cases in one comprehensive reference chart.
Detailed Explanation
Complete Sorting Algorithm Comparison
This reference provides a comprehensive side-by-side comparison of the eight most important sorting algorithms, covering all aspects that influence algorithm selection.
Time and Space Complexity
| Algorithm | Best | Average | Worst | Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| 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 | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | No |
| Shell Sort | O(n log n) | O(n log² n) | O(n²) | O(1) | No | Yes |
Adaptive Behavior
| Algorithm | Adaptive? | Behavior on Sorted Input |
|---|---|---|
| Bubble Sort | Yes | O(n) with early termination |
| Selection Sort | No | Always O(n²) comparisons |
| Insertion Sort | Yes | O(n) — best elementary sort |
| Merge Sort | No | Always O(n log n) |
| Quick Sort | Partially | Depends on pivot strategy |
| Heap Sort | No | Always O(n log n) |
| Radix Sort | No | Always O(nk) |
| Shell Sort | Yes | Benefits from partial order |
When to Use Each Algorithm
- Bubble Sort: Teaching purposes only. Never in production.
- Selection Sort: When swap count must be minimized (e.g., flash memory writes).
- Insertion Sort: Small arrays (<50 elements), nearly sorted data, online sorting.
- Merge Sort: When stability + guaranteed O(n log n) are both required. External sorting.
- Quick Sort: General-purpose in-memory sorting. Best average-case constant factor.
- Heap Sort: When O(n log n) worst-case guarantee + O(1) space are both required.
- Radix Sort: Large arrays of integers or fixed-length strings with bounded key size.
- Shell Sort: Embedded systems with limited code space. Medium-sized arrays.
Practical Comparison (10,000 Random Integers)
Approximate comparison and swap counts on uniformly random data:
| Algorithm | Comparisons | Swaps/Moves |
|---|---|---|
| Bubble Sort | ~50,000,000 | ~25,000,000 |
| Selection Sort | ~50,000,000 | ~10,000 |
| Insertion Sort | ~25,000,000 | ~25,000,000 |
| Merge Sort | ~133,000 | ~133,000 |
| Quick Sort | ~175,000 | ~65,000 |
| Heap Sort | ~240,000 | ~240,000 |
Use Case
This comparison chart serves as a quick reference for algorithm selection during software design and coding interviews. When designing a system, match your requirements (stability needed? memory constrained? worst-case guarantees? input characteristics?) to the algorithm properties in this table. Bookmark this page for quick access during development.