CLRS Solutions | Exercise 7.1-2

What value of $q$ does $\textsc{Partition}$ return when all elements in the array $A[p..r]$ have the same value? Modify $\textsc{Partition}$ so that $q = \lfloor (p+r)/2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.

Here’s the original algorithm for $\textsc{Partition}$:

$$\textsc{Partition}(A, p, r)$$$$\begin{aligned} 1& \quad x\,=\,A[r] \\ 2& \quad i\,=\,p\,-\,1 \\ 3& \quad \textbf{for }\,j\,=\,p\textbf{ to }\,r\,-\,1 \\ 4& \quad \qquad \textbf{if }\,A[j]\,\leq\,x \\ 5& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 6& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 7& \quad \text{exchange}\,A[i + 1]\,\text{with}\,A[r] \\ 8& \quad \textbf{return }\,i\,+\,1 \\ \end{aligned}$$

When all elements have the same value, the $\textsc{Partition}$ procedure behaves in a specific way. Since the pivot $x = A[r]$ equals all other elements, every comparison $A[j] \leq x$ in line 4 evaluates to true. This means the algorithm swaps every element with itself (when $i$ catches up to $j$), incrementing $i$ each time.

Starting with $i = p - 1$ and $j$ ranging from $p$ to $r - 1$, after the loop completes, we have $i = r - 1$. The final swap in line 7 exchanges $A[r]$ with $A[r - 1 + 1] = A[r]$, and the procedure returns $q = r$.

Therefore, when all elements are equal, $\textsc{Partition}$ returns $q = r$, creating a highly unbalanced split: one subarray with $n - 1$ elements and one empty subarray. This is the worst-case scenario for quicksort.

To achieve $q = \lfloor (p + r)/2 \rfloor$ when all elements are equal, we need to detect number of elements that are equal to pivot and adjust the final partition index to the left. Here’s a modified version:

$$\textsc{Modified-Partition}(A, p, r)$$$$\begin{aligned} 1& \quad x\,=\,A[r] \\ 2& \quad i\,=\,p\,-\,1 \\ 3& \quad equal\text{-}count\,=\,0 \\ 4& \quad \textbf{for }\,j\,=\,p\textbf{ to }\,r\,-\,1 \\ 5& \quad \qquad \textbf{if }\,A[j]\,=\,x \\ 6& \quad \qquad \qquad equal\text{-}count\,=\,equal\text{-}count\,+\,1 \\ 7& \quad \qquad \textbf{if }\,A[j]\,\leq\,x \\ 8& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 9& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 10& \quad \text{exchange}\,A[i + 1]\,\text{with}\,A[r] \\ 11& \quad \\ 12& \quad \textbf{/\!/} \text{ Return}\,\text{ adjusted}\,\text{ partition}\,\text{ point}\, \\ 13& \quad \textbf{return }\,(i + 1)\,-\,\lfloor\,equal\text{-}count\,/\,2\,\rfloor \\ \end{aligned}$$

The key insight is counting how many elements equal the pivot. If equal-count == r - p, then all $r - p$ elements from $p$ to $r - 1$ equal the pivot, which means (including the pivot at $r$) all elements are identical. In this case, we return the middle index.