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.
My intuition about insertion sort is "When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort." and also if your input data is already sorted the insertion sort will be fast.
What about your logic for merge sort ?
Yes both merge sort and Quick sort are comparison based sorting Algorithms they are not work manually.
comparison sort meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. so in this question there is no such case like less than etc that why i choose insertion sort as answer.