Question 19

The given array $[23, 32, 45, 69, 72, 73, 89, 97]$ contains $n = 8$ elements in strictly ascending sorted order.

Let us evaluate the number of element comparisons made by each algorithm:

• Selection sort: Always finds the minimum of remaining elements, performing $\frac{n(n-1)}{2} = \frac{8 \times 7}{2} = 28$ comparisons regardless of input order.
• Mergesort: Recursively splits and merges subarrays, requiring $\Theta(n \log_2 n) \approx 8 \times 3 = 24$ comparisons (at least 12 in the best case).
• Quicksort using last element as pivot: On a sorted array, picking the maximum element as pivot produces worst-case partitioning ($0$ and $n-1$ elements), requiring $\frac{n(n-1)}{2} = 28$ comparisons.
• Insertion sort: For an already sorted array, each element $A[i]$ is compared exactly once with its immediate predecessor $A[i-1]$ to confirm it is already in place. It performs only $n - 1 = 8 - 1 = 7$ comparisons.

Because 7 is strictly less than 28 and 12, Insertion sort uses the least number of comparisons (option C).