用Python实现归并排序算法

本文是本人在学习左神的java代码后改写为的python代码
归并排序算法的步骤是
如，对
[1, 2, 4, 9, 3, 55, 25, 64]
对分，对左半边和右半边进行递归
递归的终止条件是输入list的长度为1
如，对[11, 2, 4, 9, 3, 55, 25, 64]中
其左半边不断对分后
为[11, 2, 4, 9]
[11, 2]
[11] [2]
然后对二者进行merge
merge的规则是
开辟一个额外空间
设置左右指针，分别指左右半边的start
将更小的放在空间左边
process(arr,l,.mid)
process(arr,mid+1,r)
merge(arr,l,mid,r)

注意
1、mid = l + ((r-l)>>1)
这样即可找到奇数长度list的中点
或者偶数长度list的左中点
2、如何进行merge？
开辟的新空间是一个长度为r+1-l的数组
填充后
将空间中的元素按顺序填进
原数组arr的[l:r+1]中

def process(arr,l,r):
    if l == r:
        return 0
    mid = l + ((r-l)>>1)
    process(arr,l,mid)#0 3
    process(arr,mid+1,r) 
    merge(arr,l,mid,r)
    return arr
def merge(a,l,mid,r):
    left = l
    right = mid + 1
    temp = []
    while left <= mid and right <= r:
        if a[left] <= a[right]:
            temp.append(a[left])
            left += 1
        else:
            temp.append(a[right])
            right += 1
    while left <= mid:
        temp.append(a[left])
        left += 1
    while right <= r:
        temp.append(a[right])
        right += 1
    for i in range(l,r+1):
        a[i] = temp[i-l]
    return temp
length = 8#int(input())
arrx = [1, 2, 4, 9, 3, 55, 25, 64]#[int(x) for x in input().split(' ')]
flag = 0
direction = 1 if flag == '1' else 0
res = process(arrx,0,length-1)
resstr = ''
for x in res:
    resstr += str(x) + ' '
resstr = resstr[:-1] if direction == 0 else  resstr[:-1][::-1]
print(resstr)