Worst Case Scenario for Quicksort algorithm with pivot element n/2

Question

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.

• j_random_hacker: Read this to learn about the "final boss" of quicksort destruction: cs.dartmouth.edu/~doug/mdmspe.pdf

Answer 1

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.