Sorting Algorithms Time Complexity Chart
Comparison Table
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable? | In-Place? |
|---|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell Sort | O(n log n) | O(n log² n) | O(n log² n) | O(1) | No | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + 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 + k) | Yes | No |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Tree Sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
Visual Comparison
Time Complexity Comparison: ──────────────────────────────────────────────────────────────────── Algorithm Best Average Worst Space ──────────────────────────────────────────────────────────────────── Quick Sort n log n n log n n² log n Merge Sort n log n n log n n log n n Heap Sort n log n n log n n log n 1 Insertion Sort n n² n² 1 Selection Sort n² n² n² 1 Bubble Sort n n² n² 1 Shell Sort n log n n log² n n log² n 1 Counting Sort n + k n + k n + k n + k Radix Sort nk nk nk n + k Bucket Sort n + k n + k n² n + k Tim Sort n n log n n log n n Tree Sort n log n n log n n² n ────────────────────────────────────────────────────────────────────
Detailed Explanation
1. Comparison-Based Sorts
| Algorithm | Best Use Case | Key Characteristics |
|---|---|---|
| Quick Sort | Large datasets, general purpose | Fast average case, cache friendly |
| Merge Sort | Large datasets, stable required | Consistent O(n log n), good for linked lists |
| Heap Sort | When worst-case matters | Guaranteed O(n log n), in-place |
| Insertion Sort | Small arrays, nearly sorted | Adaptive, simple implementation |
| Selection Sort | Small arrays | Minimizes swaps, simple |
| Bubble Sort | Educational purposes | Simple but inefficient |
| Shell Sort | Medium-sized arrays | Improved insertion sort |
2. Non-Comparison Sorts
| Algorithm | Requirements | Best For |
|---|---|---|
| Counting Sort | Integer keys in small range | Small integer ranges |
| Radix Sort | Fixed-size keys | Numbers, strings with fixed length |
| Bucket Sort | Uniformly distributed data | Floating-point numbers |
3. Hybrid Sorts
| Algorithm | Composition | Use Case |
|---|---|---|
| Tim Sort | Merge + Insertion | Python's built-in sort, Java Arrays.sort() |
| Intro Sort | Quick + Heap | C++ std::sort |
Memory Usage Comparison
Memory Usage (from lowest to highest): 1. Heap Sort, Insertion Sort, Selection Sort, Bubble Sort, Shell Sort → O(1) 2. Quick Sort → O(log n) [recursion stack] 3. Tree Sort → O(n) 4. Merge Sort, Tim Sort → O(n) 5. Counting Sort, Radix Sort, Bucket Sort → O(n + k)
Stability Analysis
Stable Algorithms (preserve original order of equal elements):
Insertion Sort
Bubble Sort
Merge Sort
Counting Sort
Radix Sort
Bucket Sort
Tim Sort
Tree Sort
Unstable Algorithms:
Quick Sort
Heap Sort
Selection Sort
Shell Sort
Practical Recommendations
For Small Arrays (n < 50):
Insertion Sort - Simple and efficient for small data
For Medium Arrays (50 < n < 1000):
Shell Sort - Good balance of simplicity and efficiency
Quick Sort - With good pivot selection
For Large Arrays (n > 1000):
Quick Sort - Generally fastest in practice
Merge Sort - When stability is required
Heap Sort - When worst-case performance is critical
For Special Cases:
Nearly Sorted Data: Insertion Sort (O(n))
Small Integer Range: Counting Sort (O(n + k))
Fixed-length keys: Radix Sort (O(nk))
Uniformly distributed: Bucket Sort (O(n + k))
Real-world Usage
C++ std::sort(): IntroSort (Quick + Heap + Insertion)
Java Arrays.sort(): TimSort (Merge + Insertion)
Python sorted(): TimSort
JavaScript Array.sort(): TimSort or QuickSort (implementation-dependent)
