# 多路平衡归并排序（胜者树、败者树）

多路归并排序用作大数据集合的排序，通常因为内存资源不足，只能分段排序。
多路归并通常结合二叉树进行排序即败者树与胜者树。

1. 将无序数组分割成多个无序数组，分割成N个就是N路排序
2. 取每个无序数组的第一个元素两两排序，选取最小值或最大值，同附近的两两排序结果再次比较，直到选出最小值
3. 将最小值放在有序集合中，并将原最小值的位置替换为该无序数组段的下一个元素
4. 重复2-3步骤，直到全部排序完成

inputArr = [199383, 10, 34, -1, -32, -29, 4,
            0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
print("未排序集合:{0}".format(inputArr))
'''
将无序数组进行5路排序
N:  1       2       3       4       5
0:  199383  -32     34      1       1008
1:  10      -29     5       8
2:  34      4       4       123
3:  -1      0       36      453
'''
length=len(inputArr)
sortArr=[None]*length
groupArr=[]
# 根据无序数组大小分割成一次内存能容下的元素个数
count=4
groupCount=length//count if(length%count==0) else length//count+1
for nIndex in range(0,groupCount):    
    nStratIndex=nIndex*4
    nEndIndex=(nIndex+1)*4-1
    nEndIndex=nEndIndex if(nEndIndex<=length) else length-1
    groupArr.append([nIndex*4,nEndIndex])
    # 将每一路无序数组先排序   
    for index in range(nStratIndex+1, nEndIndex+1):
        while(index !=0):
            if(inputArr[index] > inputArr[index-1]):
                break
            inputArr[index], inputArr[index-1]\
                = inputArr[index-1], inputArr[index]
            index -= 1
sortIndex=0
while sortIndex<length:
    minGroupIndex=0
    for groupIndex in range(1,groupCount):
        minItem=inputArr[groupArr[minGroupIndex][0]]
        item = inputArr[groupArr[groupIndex][0]]
        minGroupIndex=minGroupIndex if(minItem<item) else groupIndex
    sortArr[sortIndex]=inputArr[groupArr[minGroupIndex][0]]
    groupArr[minGroupIndex][0]+=1
    if(groupArr[minGroupIndex][0]>groupArr[minGroupIndex][1]):
        groupArr.remove(groupArr[minGroupIndex])
        groupCount-=1
    sortIndex+=1
print("已排序集合:{0}".format(sortArr))