Quick sort worst case complexity improvement [closed]

Can the worst case time complexity of quick sort be changed from $$O(n^2)$$ to $$O(n\log n)$$ by modifying it?

• Yes. Just take quicksort's code and modify it so it is mergesort. – dkaeae May 17 '19 at 7:55
• Seriously, you need to restrict your "modifications" in some way; otherwise, the question is meaningless. – dkaeae May 17 '19 at 7:56
• @dkaeae Then it will be converted to merge sort which has O(nlogn) complexity in all three cases , but I want to do that without converting it to merge sort. – Mr. Suklav Ghosh May 17 '19 at 9:14

The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence $$T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n),$$ whose solution is $$T(n) = O(n\log n)$$.