# 实现原理

将数组分为两部分，左边为有序集合，右边为无序集合，
取右边集合的第一个元素与左边集合的中间位置开始对比，直到插入合适的位置后退出比较。
这种方式与直接排序基本一致，不同之处是判断应该插入中间位置的左边还是右边。

inputArr = [10, 34, 29, 4, 0, 34, 5,4,36, 1, 8]

length = len(inputArr)
print("未排序集合:{0}".format(inputArr))
# 从第1个元素开始作为无须集合
for rightIndex in range(1, length):
    insertItem=inputArr[rightIndex]
    startIndex=0
    endIndex=rightIndex-1
    # 查找最后一个中间位置
    while(startIndex!=endIndex):       
        midIndex =startIndex + (endIndex-startIndex)//2
        if(inputArr[midIndex]>insertItem):
            endIndex=midIndex
        else:
            startIndex=midIndex+1
    # 计算待插入的位置
    insertIndex=startIndex+(0 if(insertItem<inputArr[startIndex]) else 1)
    # 如果待插入位置等于当前位置则不需要移动
    if(insertIndex==rightIndex):
        continue
    # 向后平移元素
    while (insertIndex!=rightIndex):
        inputArr[rightIndex]=inputArr[rightIndex-1]
        rightIndex-=1
    # 插入正确的位置
    inputArr[insertIndex] = insertItem

print("已排序集合:{0}".format(inputArr))