Question 24

Quicksort uses the first element of each subarray as the pivot.

Input 1: $[1, 2, 3, 4, 5]$ (already sorted array):

• First call on $[1, 2, 3, 4, 5]$: pivot 1 is compared with 4 remaining elements (4 comparisons). Subarrays: empty and $[2, 3, 4, 5]$.
• Second call on $[2, 3, 4, 5]$: pivot 2 is compared with 3 elements (3 comparisons). Subarrays: empty and $[3, 4, 5]$.
• Third call on $[3, 4, 5]$: pivot 3 is compared with 2 elements (2 comparisons). Subarrays: empty and $[4, 5]$.
• Fourth call on $[4, 5]$: pivot 4 is compared with 1 element (1 comparison).
  Total comparisons $t_1 = 4 + 3 + 2 + 1 = 10$ (worst-case behavior).

Input 2: $[4, 1, 5, 3, 2]$:

• First call on $[4, 1, 5, 3, 2]$: pivot 4 is compared with 4 elements ($1, 5, 3, 2$). Elements smaller than 4 are $\{1, 3, 2\}$ and larger are $\{5\}$. (4 comparisons).
• Subarray $[1, 3, 2]$: pivot 1 is compared with 2 elements ($3, 2$). Both are larger, so $\{3, 2\}$. (2 comparisons).
• Subarray $[3, 2]$: pivot 3 is compared with 1 element ($2$). (1 comparison).
• Subarray of size 1 ($[5]$): 0 comparisons.
  Total comparisons $t_2 = 4 + 2 + 1 = 7$.

Comparing $t_1$ and $t_2$:

Hence, $t_1 > t_2$.