2
$\begingroup$

I am looking for any literature or reference for the worst case complexity of using quicksort on a sorted array with median as pivot. Different internet sources give conflicting answers and often skip this exact question or don't give logic for their answer

Can someone explain whether is it O(nlogn) or O(n^2) and why so when the array is sorted and we pick the middle element as pivot in constant time

I looked at a lot of questions on quicksort and I don't believe this has been asked before in the current form fairly close questions have been addressed

$\endgroup$
2
  • $\begingroup$ Using the median as the pivot element will result to an $O(nlogn)$ running-time for quicksort no matter the kind of input you give it. Assuming that we use the deterministic linear-time select algorithm, each recursive call will have an additional $O(n)$ overhead but the array will be divided evenly just like merge sort. And since partitioning takes $O(n) $ time also, the running-time will have the same recurrence as merge sort. $\endgroup$
    – Russel
    Aug 10, 2021 at 9:00
  • $\begingroup$ Since none of the answers are correct or directly answer the question should I even give the bounty to any one of them? $\endgroup$ Aug 13, 2021 at 5:22

3 Answers 3

2
$\begingroup$

Here is another "worst case" that isn't a sorted array, so the algorithm won't be making useless partitions, which seemed to be your concern. Consider the array $[10,30,50,70,90,100,80,60,40,20]$

Picking the median (100) as the pivot, the first partition of elements clearly takes $n$ time. If we pick the median (now 90) as the pivot again then the second partition will take $n-1$ time since the subarrays to the left and right are divided in the most unbalanced possible way. Observe how this is simply arranging one element at a time, as all the remaining elements only go to one side of the partition. With this logic, the next partition takes $n-2$ time, and so on. In such a worst case, we will have to do this for $n$ steps to finish the algorithm, making the time complexity equal to $$n+(n-1)+(n-2)+ \dots + 2=\frac{n(n-1)}{2}-1=O(n^2).$$

Interestingly, this is analogous to Selection Sort, which indeed takes $O(n^2) $ time.

As many would have mentioned, a way to improve quicksort in order to avoid such cases would be to pick a pivot uniformly at random. Note that this too, will have some worst case, but it can be shown that the probability of such a "bad" event happening every time is small.

$\endgroup$
1
$\begingroup$

"the array is sorted and we pick the middle element as pivot in constant time" -- If the array is known to be sorted, you don't need to do anything! What is typically being considered is the case when the array happens to be sorted, and the program still has to work correctly no matter what order the array is in.

As for the time complexity, it depends on the details. Using the Median of medians algorithm (note that this gives an approximate median) results in an overall time complexity of $O(n \log n)$ (but as that page notes, this is not often used in practise because of its large constant factor).

There are some common versions of quicksort that use the median of a small number of elements (as opposed to the median of the whole array) as the pivot; these have $O(n^2)$ worst-case time complexity, occurring when the small number of elements considered are always the lowest or highest. On an already sorted array, using the median of the first, middle, and last elements (one common choice) will select an optimal pivot and have $O(n \log n)$ time complexity in this case, whereas using the median of the first three elements, say, will have $O(n^2)$ time complexity in this case.

$\endgroup$
2
  • $\begingroup$ Yupp I know it's pointless to sort a sorted array but this was a question on my test what would happen if we were to use it and some analysis showed this might become the worst case if we choose the first element as the pivot but since median pivot sorting gave best results I wanted to know what would happen if we were to use it in sorting a sorted array $\endgroup$ Aug 3, 2021 at 9:18
  • $\begingroup$ Finding the median takes substantial time, so I wouldn’t assume it is fast. Since lots of people sort sorted arrays a simple method is to scan for sub arrays that are already sorted in either ascending or descending order at the beginning or end of the array, sorting the middle part and then merging with the two ends in linear time, if more than n / log n sorted items are found. $\endgroup$
    – gnasher729
    Aug 4, 2021 at 9:29
1
+25
$\begingroup$

Because of your input array $A[1...n]$ already sorted:

First check the size of the $A$ in constant time, so if size of array is odd then the median is $A[\lfloor\frac{n}{2}\rfloor]$ that can be obtain in constant time, because you have access to each indices of array $A$ in $\mathcal{O}(1)$. But if the size of array is even, you free to choose $A[\frac{n}{2}]$ as median or $A[\frac{n}{2}+1]$ as median, so we compute median in $\mathcal{O}(1)$, hence the running time of Quick sort is $$T(n)=2T(\frac{n}{2})+\mathcal{O}(1)=\mathcal{O}(n).$$

Note that, because the algorithm choose median as pivot then it partition input to half, so the worst case isn't occur.

$\endgroup$
1
  • $\begingroup$ Won't there still be for loops in our code? which give an O(n) instead of a O(1)? $\endgroup$ Aug 6, 2021 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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