用Python实现MergeSort

关于MergeSort的原理，推荐参考斯坦福的精品课程：
MergeSort --by Tim Roughgarden

废话不多说，直接上代码

import numpy as np

def merge(sorted_a,sorted_b):
    output = []
    i = 0
    j = 0
    for k in range(len(sorted_a)+len(sorted_b)):
        if i == len(sorted_a):
            output += sorted_b[j:]
            break
        elif j == len(sorted_b):
            output += sorted_a[i:]
            break
        a = sorted_a[i]
        b = sorted_b[j]
        if a < b:
            output.append(a)
            i += 1
        elif b <= a:
            output.append(b)
            j += 1
    return output

def merge_sort(arr):
    if len(arr) == 1:
        return arr[0]
    res = []
    #偶数长度时
    if len(arr)%2 == 0:
        for i in range(len(arr)//2):
            res.append(merge(list(np.array(arr[i]).flatten()),list(np.array(arr[-(i+1)]).flatten())))
            print(res)
    #奇数长度时
    else:
        lone_soul = arr[len(arr)//2]
        arr.remove(lone_soul)
        for i in range(len(arr)//2):
            res.append(merge(list(np.array(arr[i]).flatten()),list(np.array(arr[-(i+1)]).flatten())))
            print(res)
        res.append(lone_soul)
        print(res)
    return merge_sort(res)

if __name__ == '__main__':
    '''
    a = [1]
    b = [0]
    res = merge(a,b)
    print(res)
    '''
    c = [0,2,5665,4,12,3213,54654,231,2154,431,3253,213,7,123,1,65,464,619,1354,65,313,56,466,165]
    print(c,'\n-------------sorting--------------')
    sorted_c = merge_sort(c)
    print('-------------complete--------------')
    print(sorted_c)

结果如图所示：
Input: [0, 2, 5665, 4, 12, 3213, 54654, 231, 2154, 431, 3253, 213, 7, 123, 1, 65, 464, 619, 1354, 65, 313, 56, 466, 165]
-------------sorting--------------
[[0, 165]]
[[0, 165], [2, 466]]
[[0, 165], [2, 466], [56, 5665]]
[[0, 165], [2, 466], [56, 5665], [4, 313]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654], [231, 464]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654], [231, 464], [65, 2154]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654], [231, 464], [65, 2154], [1, 431]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654], [231, 464], [65, 2154], [1, 431], [123, 3253]]
[[0, 165], [2, 466], [56, 5665], [4, 313], [12, 65], [1354, 3213], [619, 54654], [231, 464], [65, 2154], [1, 431], [123, 3253], [7, 213]]
[[0, 7, 165, 213]]
[[0, 7, 165, 213], [2, 123, 466, 3253]]
[[0, 7, 165, 213], [2, 123, 466, 3253], [1, 56, 431, 5665]]
[[0, 7, 165, 213], [2, 123, 466, 3253], [1, 56, 431, 5665], [4, 65, 313, 2154]]
[[0, 7, 165, 213], [2, 123, 466, 3253], [1, 56, 431, 5665], [4, 65, 313, 2154], [12, 65, 231, 464]]
[[0, 7, 165, 213], [2, 123, 466, 3253], [1, 56, 431, 5665], [4, 65, 313, 2154], [12, 65, 231, 464], [619, 1354, 3213, 54654]]
[[0, 7, 165, 213, 619, 1354, 3213, 54654]]
[[0, 7, 165, 213, 619, 1354, 3213, 54654], [2, 12, 65, 123, 231, 464, 466, 3253]]
[[0, 7, 165, 213, 619, 1354, 3213, 54654], [2, 12, 65, 123, 231, 464, 466, 3253], [1, 4, 56, 65, 313, 431, 2154, 5665]]
[[0, 1, 4, 7, 56, 65, 165, 213, 313, 431, 619, 1354, 2154, 3213, 5665, 54654]]
[[0, 1, 4, 7, 56, 65, 165, 213, 313, 431, 619, 1354, 2154, 3213, 5665, 54654], [2, 12, 65, 123, 231, 464, 466, 3253]]
[[0, 1, 2, 4, 7, 12, 56, 65, 65, 123, 165, 213, 231, 313, 431, 464, 466, 619, 1354, 2154, 3213, 3253, 5665, 54654]]
-------------complete--------------
Output: [0, 1, 2, 4, 7, 12, 56, 65, 65, 123, 165, 213, 231, 313, 431, 464, 466, 619, 1354, 2154, 3213, 3253, 5665, 54654]

如果有什么疑问，欢迎留言！！