用python實作歸并排序

'''
Created on 2017-1-6

@author: admin
'''
from builtins import  range, int

def mergeSort(source,start,end):
    if(start>=end):
        return
    middle=int((start+end)/2)
    mergeSort(source, start, middle)
    mergeSort(source, middle+1, end)
    merge(source, start, end)

def merge(source,start,end):
    middle=int((start+end)/2)
    sortedArray=[]

    i,j=start,middle+1
    while i<=middle:
        if(j>end):break;
        if(source[i]>source[j]):
            sortedArray.append(source[j])
            j=j+1
        else:
            sortedArray.append(source[i])
            i=i+1
    if(i<=middle):
        for ii in range(i,middle+1):
            sortedArray.append(source[ii]);
    if(j<=end):
        for jj in range(j,end+1):
            sortedArray.append(source[jj])
    x=0
    for i in range(start,end+1):
        source[i]=sortedArray[x]
        x=x+1

if __name__ == '__main__':
    source=[4,1,9,2,8,7,3,6]
    mergeSort(source,0,len(source)-1)
    for i in range(0,len(source)):
        print(source[i], end=',')