Correct Option : C (Insertion Sort)
Explanation:
The given array is already sorted in ascending order.
For already sorted array, different sorting algorithms behave as following :
Selection sort :
No matter how the data is arranged, there would always be comparisons and swaps made and so the time complexity for best,average and worst case is $:O(n^2).$
In first pass, we need $n-1$ comparisons (Or $n$ comparisons, depending on the implementation)
In second pass, we need $n-2$ comparisons (Or $n-1$ comparisons, depending on the implementation) and so on.
So, the number of comparisons required by a selection sort of n items can be computed by the formula:
$(n-1) + (n-2) + \ldots + 1 = (n)(n-1)/ 2$
Or
Number of selection sort comparisons $= (n+1)(n)/ 2$
Basically, number of comparisons is $Θ(n^2)$ in all cases.
Insertion Sort :
When elements are already sorted in desired order, there are no swaps and the correct position of the element in the sorted list is the current index itself. The time complexity is $:O(n)$
Number of comparisons $= n-1$
Comparisons in total $:1 + 1 + \ldots + 1 = n − 1 \in Θ(n).$
Merge Sort :
We are dividing the list into two halves, no matter if the list is sorted or not. But if the array is sorted, while merging the list, there are no swaps merging results into an array itself. Thus, the best, average and worst case time complexity is$: O(n\log n)$
Number of comparisons, in all cases, will be $O(n\log n)$
Quick Sort :
If we use the last or first element as pivot, then Quick Sort will give worst case performance if the elements are in a sorted or reverse sorted manner. So, for the given array in the question, Quick Sort will behave in worst manner and will take $O(n^2)$ comparisons.
The best and average case time complexity is $:O(n\log n)$
Number of comparisons, in best case, will be $O(n\log n)$
So, answer will be insertion sort.
