二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

    1、从第一个元素开始，该元素可以认为已经被排序

    2、取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置

    3、将新元素插入到该位置后

    4、重复上述两步

二分插入排序是一种稳定的排序。当n较大时，总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列

#!/usr/bin/python

if __name__=='__main__':

        a=[6,1,10,4,9,3,7,5,2,8]

        k=len(a)

        for i in range(1,k):

            left=0

            right=i-1

            tmp=a[i]

            while left<=right:

                middle=(right+left)/2

                if a[middle]

                    left=middle+1

                else:

                    right=middle-1

            j=i-1

            while j>=left:

                a[j+1]=a[j]

                j-=1

            a[left]=tmp

        print a