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


closed as unclear what you're asking by Evil, David Richerby, Discrete lizard May 17 at 15:55

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Yes. Just take quicksort's code and modify it so it is mergesort. $\endgroup$ – dkaeae May 17 at 7:55
  • 2
    $\begingroup$ Seriously, you need to restrict your "modifications" in some way; otherwise, the question is meaningless. $\endgroup$ – dkaeae May 17 at 7:56
  • $\begingroup$ @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. $\endgroup$ – Suklav Ghosh May 17 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)$.

  • $\begingroup$ Is there any other way by choosing the first element as pivot rather than the median ?? $\endgroup$ – Suklav Ghosh May 17 at 9:12
  • $\begingroup$ It doesn’t have to be the median. It suffices that it break the array into two parts of linear size. $\endgroup$ – Yuval Filmus May 17 at 9:13
  • $\begingroup$ Yes , I understood , But , is there any other way?? $\endgroup$ – Suklav Ghosh May 17 at 9:15
  • $\begingroup$ Perhaps, but I’m not aware of any such way. $\endgroup$ – Yuval Filmus May 17 at 9:16
  • $\begingroup$ @SuklavGhosh There is only one way to choose the first element as pivot: you have to... choose the first. And if you do that, the worst case is quadratic. Your question doesn't make sense. $\endgroup$ – David Richerby May 17 at 12:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.