What is the running time of \(\textsc{Quicksort}\) when all elements of array \(A\) have the same value?
When all elements are identical, quicksort exhibits its worst-case behavior, resulting in \(\Theta(n^2)\) running time.
To understand why, recall how \(\textsc{Partition}\) behaves with equal elements. When the pivot \(x = A[r]\) equals all other elements, every comparison \(A[j] \leq x\) in the partitioning loop evaluates to true. This causes the algorithm to increment \(i\) for each element, ultimately placing all elements except the pivot in the left partition.
The result is that \(\textsc{Partition}\) returns \(q = r\), creating the most unbalanced split possible: the left subarray contains \(n-1\) elements (all equal to the pivot), and the right subarray is empty. This is exactly the same unbalanced partitioning that occurs when the array is already sorted.
The recursion tree has depth \(n\), with one recursive call at each level processing a subarray of size \(n-1\), \(n-2\), down to 1. The partitioning work at each level costs \(\Theta(n)\), \(\Theta(n-1)\), and so on:
\[T(n) = T(n-1) + \Theta(n)\]This is the same recurrence that we solved in Excercise 7.2-1, which tells us it would be \(\Theta(n^2)\).
This is particularly unfortunate because an array of identical elements represents a trivial sorting problem. The array is already “sorted” (all elements are equal), yet quicksort performs \(\Theta(n^2)\) comparisons.