Quick sort question

[Quest]

Excuse me if this question is novice.

Does anyone know how quick sort can be made to run in O(nlgn) time in worst case?

[Philwx]

I do not believe it is possible to do that without changing the algorithm until it is no longer "QuickSort." QuickSort has a worst case of O(n^2) , a best case of O(n) but an average case of O(nlogn). These figures are inherent in its design.

With careful optimizations based on the data you are sorting you can almost assure that it will never hit the worst case scenario, but you cannot change what its worst case scenario actually is.

You may want to try Mergesort, thought to be slower on average (in practice) but its worse case is O(nlogn) which is a better worst case scenario.

If you avoid the "worst case" of Quicksort then you are a good programmer.

If you change the worst case of Quicksort you have created a new algorithm and you get to name it.