Consider the following array: [23, 32, 45, 69, 72, 78, 89, 97] Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order? A. Selection sort B. Mergesort C. Insertion sort D. Quicksort using the last element as pivot

GATE 2021 · Algorithms · Sorting · medium

Answer: C. Insertion sort

1. Insertion sort on sorted array (n=8): For each element from index 1 to 7, compare with its immediate left neighbor. Since the array is sorted, a[i] > a[i-1] always, so only 1 comparison per element and we stop. Total = 7 comparisons.
2. Selection sort on sorted array (n=8): Selection sort always scans the remaining unsorted portion to find the minimum, regardless of whether the array is already sorted. It makes 7+6+5+4+3+2+1 = 28 comparisons.
3. Mergesort on sorted array (n=8): Mergesort always recurses and merges. For n=8, there are 3 levels. Each merge of two sorted halves of total size k requires between k/2 and k-1 comparisons. Total comparisons: approximately 17 (exact count depends on implementation but well above 7).
4. Quicksort (last element pivot) on sorted array (n=8): With last element as pivot on sorted array: pivot is always the largest element, creating partitions of size (n-1) and 0. At each level, all remaining elements are compared with the pivot. Comparisons: 7+6+5+4+3+2+1 = 28.
5. Conclusion: Comparisons: Insertion sort = 7, Mergesort ~ 17, Selection sort = 28, Quicksort = 28. Insertion sort uses the fewest comparisons.