search to locate where the ith element goes in the sorted sublistthis algorithm is called binary insert sort as general-purpose sorting algorithmthis is not practical because we then have to (on averagemove about / elements to make room for the newly inserted element in the sorted sublist but if we count only comparisonsbinary insert sort is pretty good and we can use some ideas from binary insert sort to get closer to an algorithm that uses the absolute minimum number of comparisons needed to sort consider what happens when we run binary insert sort on five elements how many comparisons do we need to dowe can insert the second element with one comparisonthe third with two comparisonsand the fourth with comparisons when we insert the fifth element into the sorted list of four elementswe need to do three comparisons in the worst case notice exactly what happens when we attempt to do this insertion we compare the fifth element against the second if the fifth is biggerwe have to compare it against the thirdand if it is bigger we have to compare it against the fourth in generalwhen is binary search most efficientwhen we have elements in the list it is least efficient when we have elements in the list sowe can do bit better if we arrange our insertions to avoid inserting an element into list of size if possible figure illustrates different organization for the comparisons that we might do first we compare the first and second elementand the third and fourth elements the two winners are then comparedyielding binomial tree we can view this as (sortedchain of three elementswith element hanging off from the root if we then insert element into the sorted chain of three elementswe will end up with one of the two posets shown on the right side of figure at cost of comparisons we can then merge into the chainfor cost of two comparisons (because we already know that it is smaller then either one or two elementswe are actually merging it into list of two or three elementsthusthe total number of comparisons needed to sort the five elements is at most seven instead of eight if we have ten elements to sortwe can first make five pairs of elements (using five comparesand then sort the five winners using the algorithm just described (using seven more comparesnow all we need to do is to deal with the original losers we can generalize this process for any number of elements aspair up all the nodes with comparisons recursively sort the winners fold in the losers we use binary insert to place the losers howeverwe are free to choose the best ordering for insertingkeeping in mind the fact that binary search has the same cost for through + items for examplebinary search requires three