moves are cmin mmin *( cave ( )/ mave ( )/ cmax ( )/ mmax ( )/ the minimal numbers occur if the items are initially in orderthe worst case occurs if the items are initially in reverse order in this sensesorting by insertion exhibits truly natural behavior it is plain that the given algorithm also describes stable sorting processit leaves the order of items with equal keys unchanged the algorithm of straight insertion is easily improved by noting that the destination sequence ai- in which the new item has to be insertedis already ordered thereforea faster method of determining the insertion point can be used the obvious choice is binary search that samples the destination sequence in the middle and continues bisecting until the insertion point is found the modified sorting algorithm is called binary insertion procedure binaryinsertion(adens _sorts *var ijmlrintegerxitembegin for : to - do : [ ] : :iwhile do :( +rdiv if [ < then : + else : end endfor : to + by - do [ : [ - enda[ : end end binaryinsertion analysis of binary insertion the insertion position is found if thusthe search interval must in the end be of length and this involves halving the interval of length log(itimes thusc si < < - log(iwe approximate this sum by the integral integral ( : - log(xdx *(log(ncc where log( /ln( the number of comparisons is essentially independent of the initial order of the items howeverbecause of the truncating character of the division involved in bisecting the search intervalthe true number of comparisons needed with items may be up to higher than expected the nature of this bias is such that insertion positions at the low end are on the average located slightly faster than those at the high endthereby favoring those cases in which the items are originally highly out of order in factthe minimum number of comparisons is needed if the items are initially in reverse order and the maximum if they are already in order hencethis is case of unnatural behavior of sorting algorithm the number of comparisons is then approximately *(log(nlog( + unfortunatelythe improvement obtained by using binary search method applies only to the number of comparisons but not to the number of necessary moves in factsince moving itemsi keys and associated informationis in general considerably more time-consuming than comparing two keysthe