# 原理

定义一个同样大小数组来存方排序结果，并定义最小/最大值变量用来记录索引。
当无序集合的元素小于最小值时插入左边也就是`索引减一`的位置，
如果大于最大值则是在右边`索引加一`的位置,
其它情况按折半/直接方式插入。

inputArr = [199383, 10, 34, -1,-32,-29, 4, 0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
length = len(inputArr)
sortArr = [None]*length
minIndex=maxIndex=0
sortArr[0]=inputArr[0]
print("未排序集合:{0}".format(inputArr))
for index in range(1, length):
    item=inputArr[index]
    # 小于最小值的放左边
    if(item<sortArr[minIndex]):
        minIndex=(minIndex-1+length)%length
        sortArr[minIndex]=item
        continue
    # 大于最大值的放右边
    if(item>sortArr[maxIndex]):
        maxIndex=(maxIndex+1+length)%length
        sortArr[maxIndex]=item
        continue
    # 大于最小值，小于最大值的情况需要移位插入
    else:        
        # 将最大数向后移动1位
        sortArr[(maxIndex+1+length)%length]=sortArr[maxIndex]
        # 再原来的最大数位置插入待插入的值
        sortArr[maxIndex]=item
        # 逐个向左比较，直到找到它的正确位置
        preIndex=maxIndex
        while(sortArr[preIndex]<=sortArr[preIndex-1]):
            sortArr[preIndex],sortArr[preIndex-1]=sortArr[preIndex-1],sortArr[preIndex]
            preIndex=(preIndex-1+length)%length
        maxIndex=(maxIndex+1+length)%length
print("已排序集合:{0},min:{1},max:{2}".format(sortArr,minIndex,maxIndex))