I recently wrote a written test for the recruitment of Scientists/Engineers in ISRO(Indian Space Research Organization) few days back and the following question appeared in the test.
Of the following algorithms, which has execution time that is least dependent on initial ordering of the input?
- Insertion Sort
- Quick Sort
- Merge Sort
- Selection Sort
Well if array is sorted, when we are doing 2 way merge always the left subarray will get exhausted and we have to simply fill in the right sub array. So, number of comparisons will be equal to length of left subarray everytime. In selection sort, if array is already sorted, number of comparisons will be the same as that of the worst case, however the index of minimum element will change only after 1 full pass.
In worst case, number of comparisons in 2 way merge will be (length of left subarray+length of right subarray-1). In selection sort, worst case minimum element's index will keep on changing after every comparison.
Only 1 option can be correct. So, what's the best answer?