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?
This is a case of almost sorted array and insertion sort works best in these cases..
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.
So that's why it is Insertion Sort.
*NOTE- Stable Sort Algorithm are- Insertion sort, Merge sort, Bubble sort, Selection sort.