Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of…

Key idea: the array is already sorted in ascending order.

Because the input is already sorted, insertion sort runs in its best case and needs only n−1 element comparisons (each element compared once to its predecessor). With n = 8 this is 7 comparisons.

• Selection sort: always does n(n−1)/2 comparisons, which for n = 8 is 28.

• Mergesort: Θ(n log n) comparisons; for n = 8 this is on the order of 24 comparisons, larger than 7.

• Quicksort with last-element pivot: on a sorted array this gives the worst-case (quadratic) behavior, about n(n−1)/2 ≈ 28 comparisons.

Conclusion: Insertion sort uses the fewest element-to-element comparisons (7) on this already sorted array, so it is the best choice among the given algorithms for minimizing comparisons.