归并排序的思想是先递归分解数组，再合并数组，将数组分解最小之后，然后合并两个有序数组，基本思想就是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可

# -*- coding: utf-8 -*-
"""
归并排序：
merge_sort  54 26 93 17 77 31 44 55 56
..............................................................
拆：
           54 26 93 17           77 31 44 55 56
        54 26      93 17      77 31    44 55 56
    54  26      93  17      77  31    44  55 56
...............................................................
合：
    26 54      17 93        31 77     44 55 56
    R           L           R          L
    17 26 54 93         31 44 55 56 77
    R                   L
    17 26 31 44 54 55 56 77 93
...............................................................
"""
def merge_sort(alist):
    n=len(alist)
    if n<=1:
        return alist
    mid=n//2
    # left 采用归并排序后形成的有序的新得列表
    left_li=merge_sort(alist[:mid])

    right_li=merge_sort(alist[mid:])

    # 将两个有序的子序列合并为一个新得整体
    # merge(left,right)

    left_pointer, right_pointer =0,0
    result=[]
    while left_pointer<len(left_li) and right_pointer<len(right_li):
        if left_li[left_pointer] <right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer +=1
        else:
            result.append(right_li[right_pointer])
            right_pointer +=1
    result +=left_li[left_pointer:]
    result +=right_li[right_pointer:]
    return result
if __name__ == '__main__':
    li =[54,26,93,17,77,31,44,55,20]
    print(li)
    sorted_li=merge_sort(li)
    print(li)
    print(sorted_li)