0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ The behaviour of Quicksort on inputs with duplicates depends on the specifics of the implementation. Which one are you investigating? $\endgroup$ – Raphael♦ Jan 12 '14 at 21:49
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you summarise the results shortly? $\endgroup$ – Raphael♦ Jan 30 '14 at 10:30
0
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jan 12 '14 at 21:03

Your Answer

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