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

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

| cite | improve this answer | |
  • $\begingroup$ Is there any other way by choosing the first element as pivot rather than the median ?? $\endgroup$ – Mr. Suklav Ghosh May 17 '19 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 '19 at 9:13
  • $\begingroup$ Yes , I understood , But , is there any other way?? $\endgroup$ – Mr. Suklav Ghosh May 17 '19 at 9:15
  • $\begingroup$ Perhaps, but I’m not aware of any such way. $\endgroup$ – Yuval Filmus May 17 '19 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 '19 at 12:48

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