0
$\begingroup$

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the worst case occurs if:

  1. Array is already sorted in same order
  2. Array is already sorted in reverse order
  3. All elements are same

and that the complexity in that cases is $\mathcal{O}({n^2})$. However, this cases should not be a problem if I take the middle index of the partition as my pivot element.

$\endgroup$
3
$\begingroup$

Since you're not guaranteed anything about the order of the input, it's possible that the n/2 position has the smallest/largest element of the input. Then quicksort will proceed and put everything else on one side of the pivot.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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