chap lower bounds or figure organizing comparisons for sorting five elements first we order two pairs of elementsand then compare the two winners to form binomial tree of four elements the original loser to the root is labeled aand the remaining three elements form sorted chain (forming sorted chain of four elementswe then insert element into the sorted chain finallywe put into the resulting chain to yield final sorted list figure merge insert sort for ten elements first five pairs of elements are compared the five winners are then sorted this leaves the elements labeled - to be sorted into the chain made by the remaining six elements comparisons in the worst case for lists of size or so we pick the order of inserts to optimize the binary searcheswhich means picking an order that avoids growing sublist size such that it crosses the boundary on list size to require an additional comparison this sort is called merge insert sortand also known as the ford and johnson sort for ten elementsgiven the poset shown in figure we fold in the last four elements (labeled to in the order element element element and finally element element will be inserted into list of size threecosting two comparisons depending on where element then ends up in the listelement will now be inserted into list of size or costing two comparisons in either case depending on where elements and are in the listelement will now be inserted into list of size or all of which requires three comparisons to place in sort order finallyelement will be inserted into list of size or