Quick sort
Worst case complexity
n log n
Sorting algorithms
Algorithm complexity

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.

Practice algorithms

Quick sort is one of the most popular and efficient sorting algorithms widely used due to its average-case performance of O(nlog⁡n)O(n \log n). However, its worst-case performance can degrade to O(n2)O(n^2), 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 O(nlog⁡n)O(n \log n) 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:

  1. Choose a pivot element from the array.
  2. Partition the array into two sub-arrays:
    • Elements less than the pivot
    • Elements greater than or equal to the pivot
  3. 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 O(nlog⁡n)O(n \log n) complexity.
  • A poor choice, like the smallest or largest element repeatedly, results in highly unbalanced partitions, leading to a worst-case complexity of O(n2)O(n^2).

Achieving O(nlog⁡n)O(n \log n) Worst-Case Complexity

While the classical Quick sort has a best and average-case time complexity of O(nlog⁡n)O(n \log n), 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 O(n2)O(n^2) 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 2log⁡(n)2\log(n).
  • Heap Sort: Guarantee O(nlog⁡n)O(n \log n) 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 O(nlog⁡n)O(n \log n).

Practical Considerations

While achieving O(nlog⁡n)O(n \log n) 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

MethodDescriptionComplexity
Median-of-ThreeChoose the median of first, middle, and last elementAverage O(nlog⁡n)O(n \log n) Worst-case near O(nlog⁡n)O(n \log n)
Randomized Quick SortRandomly select pivotAverage O(nlog⁡n)O(n \log n) Expected O(nlog⁡n)O(n \log n)
IntrosortCombines Quick, Heap, Insertion SortWorst-case O(nlog⁡n)O(n \log n)
Median-of-MediansDeterministic median selectionGuaranteed O(nlog⁡n)O(n \log n) in worst case

Conclusion

While it's possible to achieve an O(nlog⁡n)O(n \log n) 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.


Course
Intermediate
27 lessons
15 hours
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 course
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.

Practice algorithms