Can we do Quick sort with n logn worst case complexity?

Question

I was wondering if we can somehow modify the Quick sort algorithm to produce the worst case time complexity of O(n logn). Although this can be done by permuting data and then assuming that we will get the average case complexity rather than worst case. But this is not a full proof solution as we can again land into worst case after permuting. Is there any other way around that you can suggest.

Answer 1

Well, Yes we can bring it down to O(nlogn). All the algorithms I have seen that try to bring this down are based on choosing your pivot point. If you can "intelligently" choose your pivot point it can be brought down.

Options 1. Intro Sort . It is no longer a "pure" quick sort now. It uses merge sort later on. 2. Choosing the median as a pivot. Now finding the median might take a huge amount of time if done in the normal way BUT there is a mention in the Introduction to Algorithms.

Here is something straight from the horse's mouth Introduction to Algorithms

1. Divide the array into [n/5] groups with each group having 5 elements
2. Find median of each group using insertion sort and then pick the median from this list
3. Then you will need to recursively try and find the median of [n/5] medians calculated from each group.
4. Partition the array around this median

There are some more complex stuff in this algorithm that I have hidden. You can go through it in the same book if you want. Usually, I don't try to use this algorithm. I use a randomized selection operation to find the pivot and work on with that.

Answer 2

Well "modify" is a rather subjective word here. There are a number of ways you can augment quicksort to make it run in O(n log n). Whether or not you could still call it a quick sort is to be determined.

One of which is introsort. Introsort starts with quicksort but then switches to merge sort which has worst-case complexity O(n log n). One of the purposes of introsort is to combat median-of-3 killer lists.