Consider the following array. Which algorithm among the given options uses the least number of comparisons (among the array elements) to sort the array in ascending order?

Question

Accepted Answer

Correct answer: A — Concept A sorting algorithm's comparison count can depend on how the input elements are already arranged, or it can be fixed by the algorithm's own structure regardless of order. Selection sort always makes the same number of comparisons no matter how the input starts, because it unconditionally scans the entire remaining unsorted portion on every pass; merge sort's comparison count stays within the same Θ(n·log2n) order of growth for any arrangement, since it always performs the same divide-and-merge recursion, though the exact count can vary slightly with the data. Insertion sort and quicksort with a fixed-position pivot are both far more order-sensitive, but in opposite directions: insertion sort's fewest comparisons occur when the array is already sorted, whereas a naive quicksort's most comparisons occur on exactly that same already-sorted input. Application to this array The array has n = 8 elements, [23, 32, 45, 69, 72, 73, 89, 97], and it is already arranged in ascending order. Algorithm Comparisons for this input Why Insertion sort n − 1 = 7 Each pass only confirms the current element is not smaller than its predecessor; no shifting is needed on already-sorted data. Selection sort n(n − 1)/2 = 28 Every pass scans the entire remaining unsorted portion to find the minimum, regardless of the existing order. Quicksort (last element as pivot) n(n − 1)/2 = 28 The pivot is always the largest remaining value, so every partition splits into one empty side and one side with everything else — the worst-case split. Merge sort 12 (this array) Because the array is already sorted, each merge step consumes the entire left half before touching the right half, so every merge takes the minimum possible comparisons for its size — still more than insertion sort's 7. Cross-check Insertion sort's best-case running time is Θ(n), achieved precisely on an already-sorted array, which needs exactly n − 1 comparisons — matching the 7 comparisons computed above. No method here can do fewer than n − 1 comparisons, because confirming that a sequence of n elements is fully sorted requires enough pairwise comparisons to connect all n elements into a single chain; fewer than n − 1 comparisons would leave at least one adjacent pair's relative order unconfirmed. This does not contradict the general Ω(n·log2n) lower bound for comparison-based sorting, because that bound applies to the worst case (or the average case) across all possible arrangements, not to a single best-case instance like this one. Result Insertion sort needs only n − 1 = 7 comparisons for this array — fewer than selection sort, quicksort with a last-element pivot, or merge sort all require for the same 8 elements — so it is the algorithm that uses the least number of comparisons here.

Answer

A. Insertion sort

Answer

B. Selection sort

Answer

C. Quicksort using the last element as pivot

Answer

D. Merge sort

Algorithm	Comparisons for this input	Why
Insertion sort	n − 1 = 7	Each pass only confirms the current element is not smaller than its predecessor; no shifting is needed on already-sorted data.
Selection sort	n(n − 1)/2 = 28	Every pass scans the entire remaining unsorted portion to find the minimum, regardless of the existing order.
Quicksort (last element as pivot)	n(n − 1)/2 = 28	The pivot is always the largest remaining value, so every partition splits into one empty side and one side with everything else — the worst-case split.
Merge sort	12 (this array)	Because the array is already sorted, each merge step consumes the entire left half before touching the right half, so every merge takes the minimum possible comparisons for its size — still more than insertion sort's 7.

Consider the following array. Which algorithm among the given options uses the…