Can we do Quick sort with n logn worst case complexity?
Data Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.
Quick sort is one of the most popular and efficient sorting algorithms widely used due to its average-case performance of . However, its worst-case performance can degrade to , primarily when the selected pivot divides the array in a highly unbalanced manner. This naturally raises the question: Can we modify or use a version of Quick sort that guarantees an worst-case complexity?
Understanding Quick Sort
Quick sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
Algorithm Steps:
- Choose a pivot element from the array.
- Partition the array into two sub-arrays:
- Elements less than the pivot
- Elements greater than or equal to the pivot
- Recursively apply the above steps to the sub-arrays.
The choice of the pivot impacts the efficiency:
- A good choice results in balanced partitions, leading to complexity.
- A poor choice, like the smallest or largest element repeatedly, results in highly unbalanced partitions, leading to a worst-case complexity of .
Achieving Worst-Case Complexity
While the classical Quick sort has a best and average-case time complexity of , we can attain the same complexity for the worst-case scenario through several strategies:
1. Median-of-Three Pivot Selection
To prevent consistently poor pivot choices, consider using the median of three method:
- Choose three elements: the first, middle, and last elements of the array.
- Use the median of these three as the pivot.
This method shields the algorithm from the disastrous impact of already sorted or reverse-sorted arrays, thus improving performance toward more balanced partitions.
2. Randomized Quick Sort
Randomized Quick sort employs randomization in pivot selection to mitigate the risk of poor choices:
- Pick a random element from the array as a pivot.
- This randomization virtually ensures against the worst-case complexity because it breaks the assumption of having consistently unfavorable input.
3. Introsort
Introsort, or introspective sort, combines Quick sort, Heap sort, and Insertion sort. The algorithm begins with Quick sort and switches to Heap sort if the recursion depth exceeds a certain level:
- Quick Sort: If further splitting doesn't achieve a significant enough size reduction, switch when the depth exceeds .
- Heap Sort: Guarantee worst-case time complexity.
- Insertion Sort: Optimize smaller segments for performance gains.
4. Deterministic Selection Algorithms (e.g., Median of Medians)
The Median-of-Medians algorithm can be employed to select a good pivot:
- Split the array into groups of five elements.
- Sort each and extract the medians.
- Use the median of these medians as the pivot.
This deterministic method leads to balanced partitions, ensuring the worst-case time complexity remains .
Practical Considerations
While achieving in the worst case is theoretically appealing, the added complexity in implementation and the constant factors involved in these approaches often make them slower in practice for most datasets.
Comparison Table
| Method | Description | Complexity |
| Median-of-Three | Choose the median of first, middle, and last element | Average Worst-case near |
| Randomized Quick Sort | Randomly select pivot | Average Expected |
| Introsort | Combines Quick, Heap, Insertion Sort | Worst-case |
| Median-of-Medians | Deterministic median selection | Guaranteed in worst case |
Conclusion
While it's possible to achieve an worst-case complexity with modifications to the traditional Quick sort, these variations require additional computational overhead or complexity. For many practical applications, especially where data patterns are unpredictable, utilizing a randomized Quick sort or introspective sort provides a robust balance between average performance and worst-case guarantees. However, the choice of the sorting algorithm should always consider the specific use case, constraints, and typical data distributions.
Related reading
- Can we solve this Sock Merchant problem in less complexity?
- Can we use binary search tree to simulate heap operation?
- Can we use Morris Traversal for postorder?
- Can we use Normal Equation for Logistic Regression ?
- Candidate Elimination Algorithm
- Candidate Elimination Algorithm
- Cannot understand this prime generator algorithm in my textbook
- Cardinal direction algorithm in Java

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseData Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.