Meena is working in an IT company as HR manager. She has a large list of potential candidates to be recruited which are all sorted by their names. But she found that due to a bug in software 'O' was treated as '0' by the input reader and hence the sorted list is not correct. What would be the appropriate algorithm to correct the list of candidate profiles?

Since among the option only Merge sort and Insertion sort are Stable Sort algorithm and it is been said that the list is already sorted by name, so in best case Merge sort takes O(nlogn) time and Insertion sort takes O(n) times.

Time complexity of insertion sort is of same order as the number of inversions in the input. Now, see the maximum possible inversions in this question.

when O is treated as 0, all those names will be top in list, but actually it should come after M. so what we have to do is to jump 1-9 and A-M in list and after that we have to put those names with O. This makes number of invertions fixed. Did i think right, sir?

Sorted input for quick sort is Worst case input...where as for merge sort it remains O(logn) but for insertion sort it just takes O(n) time i.e one pass...