Quicksort's asymptotic performance for array of [50,…,50,100,…100]

Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort.

I think it it should be $O(n^2)$ as for array of same elements the complexity is $O(n^2)$ and this particular problem could be rewritten as sorting the first half + sorting the second hald $O(2*(\frac{n}{2})^2 + n)$ which is still $O(n^2)$.

But my schoolmates claim it should be $O(n log(n))$.. so which one is correct?

• The behaviour of Quicksort on inputs with duplicates depends on the specifics of the implementation. Which one are you investigating? – Raphael Jan 12 '14 at 21:49

That depends very much on exactly what quicksort variant you use. Perhaps you should take a peek at Sedgewick "Quicksort with equal keys", SIAM J. Comp 6:2 (jun 1977), pp 240-267 (get it here) or Bentley, McIllroy "Engineering a sort function", Software: Practice & Experience 23:11 (nov 1993), pp 1249-1265.

• Can you summarise the results shortly? – Raphael Jan 30 '14 at 10:30

We can observe the input array given to the algorithm is already sorted. So at each step, the array is partitioned into two subarrays of size $n-1$ and 0 (why?). This gives us the recurrence $T(n) = T(n-1) + T(0) + \Theta(n)$. Can you now bound $T(n)$, and answer your question?

• Depending on how you choose the pivot and exactly how you implement it, the first split might actually be 50/50, though this won't change the asymptotic complexity by more than a constant factor. – David Richerby Jan 12 '14 at 21:03