Good evening,
I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of self-study.
By quicksort, I'm referring to an algorithm that begins by taking the first element of the initial list (the pivot; let's call it $a_1$) and forms two sublists, the first containing those elements that are less than $a_1$, in the order they arise, and the second containing those elements greater than $a_1$, in the order they arise. Then, it puts $a_1$ at the end of the first list. This procedure is successively repeated recursively for each sublist, until each sublist contains one item.
My question is: Every source about this subject seems to agree that the worst case scenario is when the list to be sorted is already sorted and the pivot is the smallest element on the list. In this case, the total number of comparisons is $n(n - 1)/2$, where $n$ is the number of items in the list (for example, see here: http://www.daniweb.com/software-development/cpp/threads/171145).
But it seems to me that the worst case happens when the list is sorted in decreasing order and the pivot is the first element in the list, which, in this case, would be the greatest element on the list.
For example, consider the list $\{4, 3, 2, 1\}$. I will chose the pivot as the first element. Each step of the quicksort will divide the original list as follows, according to the description I gave above:
In the first step, $\{4, 3, 2, 1\}$ is divided into two lists: $\{3, 2, 1, 4\}$ (elements smaller than the pivot plus the pivot appended in the end) and $\{\}$ (elements greater than the pivot: empty list). The first step requires 3 comparisons to find that 3, 2, 1 are smaller than 4.
Similarly, in the second step, the list $\{3, 2, 1, 4\}$ is divided into $\{2, 1, 3\}$ and $\{4\}$, requiring 3 comparisons (to find that 2, 1 are smaller than 3 and 4 is greater than 3). The third step divides $\{2, 1, 3\}$ into $\{1, 2\}$ and $\{3\}$, requiring 2 comparisons. The last step divides $\{1, 2\}$ into $\{1\}$ and $\{2\}$, requiring 1 comparison.
If I sum the number of comparisons for each step, I find $3 + 3 + 2 + 1 = 9$. In fact, if I generalize the above situation to $n$ elements sorted in decreasing order, with the first element as the pivot, I get $n(n - 1)/2 + n - 1$ comparisons.
If the list was sorted in increasing order $\{1, 2, 3, 4\}$ and I chose the pivot to be the smaller element on the list (in this case, the first element), the number of comparisons would be $n(n - 1)/2 = 4(3)/2 = 6$.
9 comparisons is greater than 6 comparisons. Why isn't it the worst case?
Thank you in advance.