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?

  1. Insertion Sort
  2. Quick Sort
  3. Merge Sort
  4. 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.