# Does quicksort for increasing order work faster if the input set is more decreasing sorted?

The following procedure implements quicksort:

QUICKSORT(A; p; r)
1 if p < r
2 q D PARTITION(A; p; r)
3 QUICKSORT(A; p; q-1)
4 QUICKSORT(A; q+1; r)


To sort an entire array A, the initial call is QUICKSORT(A; 1; A.length). The key to the algorithm is the PARTITION procedure, which rearranges the subarray A[p..r] in place.

PARTITION(A; p; r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4     if A[j] <=   x
5         i = i + 1
6         exchange A[i] with A[j]
7 exchange A[i+1]  with A[r]
8 return i +1


The quicksort algorithm sorts a set in increasing order, where the pivot is chosen to be the last element in the current array.

I am trying to figure out the worse case and best case to the algorithm.

But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.

After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.

Is it correct that

• when the input set is already in decreasing order, the assignments and exchanges in the for loop in PARTITION will be skipped?

• Does quicksort work faster when the input set is already more sorted in decreasing order?

Thanks.

• What have you tried and where did you get stuck? Which research papers have you read? These issues have definitely been studied. Note that the particular choice of partitioning algorithm is important here, less so the Quicksort wrapping, so you may want to search for results on partitioning. – Raphael Nov 15 '16 at 12:41

First, this is not the Quicksort that we all know and love, but some rather strange version of it, so your results cannot be applied to what is usually called Quicksort.

If the array is already in descending order, your version (unlike the original Quicksort) will not do any exchanges in the first partitioning. So the partitioning will be fast. However, it makes practically no progress; only one element is moved to its right position, and you will have about $n^2 / 2$ comparisons in total, which is about the worst case possible.

An array in ascending order is even worse, since you will do $n^2/2$ comparisons, plus \$n^2/2 exchange operations.

• What is the Quicksort that you all know and love? – Tim Jan 14 '17 at 22:38
• Partitioning starts both at the left and the right, until it finds an element > pivot on the left, and an element < pivot on the right, and exchanges them. – gnasher729 Jan 15 '17 at 9:33
• And typically you wouldn't take the first or last element the pivot, because that makes sorts and reverse sorted take quadratic time. – gnasher729 Jan 15 '17 at 21:58