# 归并排序（2-路归并排序）

将无序集合拆分成只有一个元素的有序集合，然后两两合并排序，直到合成一个包涵所有元素的有序集合。

原始集合：{5,2,4,6,8,1,9,7,10,3}
拆分直到只要一个元素的集合：
{5,2,4,6,8,1,9,7,10,3} => {5}{2}{4}{6}{8}{1}{9}{7}{10}{3}
合并排序：
{5}{2}{4}{6}{8}{1}{9}{7}{10}{3}=>{5,2}{4,6}{8,1}{9,7}{10,3}=>{2,5}{4,6}{1,8}{7,9}{3,10}
再次合并：
{2,5}{4,6}{1,8}{7,9}{3,10}=>{2,5,4,6}{1,8,7,9}{3,10}=>{2,4,5,6}{1,7,8,9}{3,10}
再次合并：
{2,4,5,6}{1,7,8,9}{3,10}=>{2,4,5,6,1,7,8,9}{3,10}=>{1,2,4,5,6,7,8,9}{3,10}
最后合并：
{1,2,4,5,6,7,8,9}{3,10}=>{1,2,4,5,6,7,8,9,3,10}=>{1,2,3,4,5,6,7,8,9,10}

inputArr = [199383, 10, 34, -1, -32, -29, 4,
            0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]

length = len(inputArr)
print("未排序集合:{0}".format(inputArr))
gap=1
groupCount = length
while(groupCount>=1):
    if(groupCount<length):
        for gapIndex in range(0, groupCount):
            startIndex = gapIndex*gap
            endIndex = ((startIndex+gap) if((startIndex+gap) < length) else length)
            for index in range(startIndex, endIndex): 
                for maxIndex in range(startIndex+1, endIndex-index):
                    if(inputArr[maxIndex-1] > inputArr[maxIndex]):
                        inputArr[maxIndex-1], inputArr[maxIndex] =\
                            inputArr[maxIndex], inputArr[maxIndex-1]
    # 最后一次分组合并排序时groupCount一定为1，执行完此次排序后排序结束，break跳出while循环借宿排序
    if(groupCount==1):
        break
    # 就近两个集合的元素个数
    gap *= 2
    # 如果元素个数大于长度则设置为元素个数，避免gap>length
    gap=(gap if(gap<length) else length)
    groupCount=length//gap+length % gap
print("已排序集合:{0}".format(inputArr))