Question-5

What is the least number of comparisons required among the array elements to sort the given array in ascending order using the following sorting algorithms?

23, 32, 45, 69, 72, 73, 89, 97

• Quicksort using the last element as a pivot
• Selection sort
• Mergesort
• Insertion sort

Answer

• Quicksort using the last element as a pivot
• Selection sort
• Mergesort
• Insertion sort

Solution

The given array is already sorted. Insertion sort takes the least number of comparisons \(O(n)\) in this case because, for a number to be inserted into an already sorted array, only one comparison is required. Hence, Insertion sort uses the least number of comparisons in this scenario.