You have to sort a list $L$, consisting of a sorted list followed by a few ‘random’ elements. Which of the following sorting method would be most suitable for such a task ?
From given description, the list is "almost sorted".
Answer Insertion sort
since list is almost sorted followed only few random elements these elements will easily and quickly take their position(or inserted in the list) one after another by insertion sort as there is least no of shifting is needed
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
Nobody explained it correctly every1 just gave roundabout answer (theory etc ) sh!va gave the fact but why the fact is that only insertion sort does not only in place but also when it's sorting it's not concerned with what is at right of the element being sorted only it sees left which by god's grace on the algo will be perfectly sorted(see the match to the question). i.e. it's local in it's approach. That also full portion of the loop not like in inner loop & again going out on out ward loop or something means half/portion of algorithm saved.
64.3k questions
77.9k answers
244k comments
80.0k users