Algorithm analysis Binary search is quicker than sequence search, So the average performance of binary insertion sort is better than direct insertion sort The number of key comparison have nothing to do with the initial order of objects to be sort, but depend on the number of objects. it needs the number of Llog,i +1 key comparison when inserting the ith object. so if we need to insert n objects, the number of key comparison is as follows ∑dg2l」 g,l+1)≈n·l0g,n◼ Binary search is quicker than sequence search, so the average performance of binary insertion sort is better than direct insertion sort. ◼ The number of key comparison have nothing to do with the initial order of objects to be sort, but depend on the number of objects. it needs the number of log2 i +1 key comparison when inserting the ith object. so if we need to insert n objects, the number of key comparison is as follows： (   ) − = +   1 1 2 2 log 1 log n i i n n Algorithm analysis