GATE CS 2021 Set 1 Q9 — Searching, Sorting, Hashing

The given array is already sorted in ascending order:

$$\text{Array: } [23, 32, 45, 69, 72, 73, 89, 97] \quad (n = 8)$$

Let us analyze the number of element comparisons required by each sorting algorithm on an already sorted array of size $n = 8$:

• Insertion Sort:
  For an already sorted array, each element from index $1$ to $n-1$ is compared exactly once with its immediate predecessor to confirm its correct position.
  $$\text{Total comparisons} = n - 1 = 8 - 1 = 7$$
• Selection Sort:
  Selection sort always performs the same number of comparisons regardless of the initial order of the array.
  $$\text{Total comparisons} = \frac{n(n-1)}{2} = \frac{8 \times 7}{2} = 28$$
• Mergesort:
  Mergesort uses a divide-and-conquer approach. For $n = 8$, the array is split into subarrays and merged. In the best-case merging scenario (which occurs here), the number of comparisons is:
  $$\text{Total comparisons} = 4 \times 1 \text{ (level 1)} + 2 \times 2 \text{ (level 2)} + 1 \times 4 \text{ (level 3)} = 12$$
• Quicksort (with last element as pivot):
  Since the array is already sorted, choosing the last element as the pivot always results in the most unbalanced partitions (worst-case behavior).
  $$\text{Total comparisons} = \frac{n(n-1)}{2} = 28$$

Comparing the results, Insertion Sort requires the least number of comparisons ($7$).