Question

Consider the following array:
\[ 23 32 45 69 72 73 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

Hint:

Insertion sort is highly efficient for nearly sorted or fully sorted arrays due to its linear-time best case.

Answer 1

The Correct Option is C

Step 1: Examine the given array.
The array is already sorted in ascending order.

---

Step 2: Analyze Insertion Sort behavior.
Insertion sort performs optimally when the input array is already sorted.

Each element is compared only once with its immediate predecessor, resulting in exactly n − 1 comparisons for an array of size n.

---

Step 3: Compare with other sorting algorithms.

Selection Sort:
Always performs n(n − 1)/2 comparisons, independent of the input order.

Merge Sort:
Requires Θ(n log n) comparisons even when the array is already sorted.

Quick Sort (last element as pivot):
For a sorted array, this choice of pivot leads to the worst-case behavior with Θ(n²) comparisons.

---

Final Conclusion:
Among the given algorithms, Insertion Sort uses the least number of comparisons when the array is already sorted.