Best Case vs Worst Case — Sorting Algorithm Analysis
Compare best-case and worst-case time complexity across all major sorting algorithms. Understand what input patterns trigger each case and how to avoid worst-case scenarios.
Detailed Explanation
Understanding Best and Worst Cases
Every sorting algorithm has different performance characteristics depending on the input data. Understanding when each case occurs is essential for choosing the right algorithm.
Complexity Comparison Table
| Algorithm | Best Case | Average | Worst Case | Worst-Case Trigger |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Reverse sorted |
| Selection Sort | O(n²) | O(n²) | O(n²) | Always the same |
| Insertion Sort | O(n) | O(n²) | O(n²) | Reverse sorted |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Always the same |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | Sorted + bad pivot |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | Always the same |
| Radix Sort | O(nk) | O(nk) | O(nk) | Always the same |
| Shell Sort | O(n log n) | O(n log² n) | O(n²) | Depends on gaps |
What Triggers Worst Cases
Bubble Sort and Insertion Sort: The worst case occurs when the array is in reverse order, maximizing the number of comparisons and swaps. Every element must travel the maximum distance.
Quick Sort: The worst case occurs when the pivot consistently divides the array into one element and n-1 elements. This happens with sorted/reverse-sorted input using first or last element as pivot.
Shell Sort: The original Shell gap sequence (n/2, n/4, ...) produces O(n²) worst case because certain arrangements of elements are never compared until the final gap-1 pass.
Algorithms Immune to Input Order
Merge Sort, Heap Sort, and Radix Sort always perform the same number of operations regardless of input order. This makes them predictable but means they cannot take advantage of partially sorted input (unlike Insertion Sort or Timsort).
Amortized and Expected Complexity
Quick Sort with randomized pivot selection has O(n log n) expected time, meaning the average over all possible random choices is O(n log n), even though any single run could theoretically be O(n²). The probability of O(n²) behavior decreases exponentially with n.
Use Case
Understanding best and worst cases is crucial for system design and algorithm selection. In real-time systems where worst-case guarantees matter (avionics, medical devices), Heap Sort or Merge Sort are preferred. In typical applications where average performance matters more, Quick Sort (with random pivot) is the standard choice. For interview preparation, being able to explain when and why each case occurs demonstrates deep algorithmic understanding.