归并排序

基本思想

核心思想是“分治法”。 将序列看成nge有序的子序列，每个序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列，然后再两两归并······这样重复下去，直到得到一个长度为n的有序序列，这种排序方法叫做2-路归并算法。依次类推，还有3-路归并排序等等。

如何有效的将两个有序序列合并

从比较两个序列的第一个元素，谁比较小就取谁，取了之后删除这个元素，然后继续比较；如果有一个序列为空，直接把不为空的序列依次取出即可。

python实现

# 合并两个有序序列
def merge(left, right):
    l, r = 0, 0
    # 存储取出的元素
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    # 有序列为空的时候，直接把不为空的序列拼接
    result += left[l:]
    result += right[r:]
    return result


# 将序列分为两组，如果都有序，则可以直接合并，不然继续分成两组
def mergeSort(alist):
    if len(alist) <= 1:
        return alist
    mid = len(alist) // 2
    # 左边有序
    left = mergeSort(alist[:mid])
    # 右边有序
    right = mergeSort(alist[mid:])
    # 将两个有序序列合并
    return merge(left, right)


if __name__ == '__main__':
    a = [29, 10, 28, 17, 19, 14, 20]
    result = mergeSort(a)
    print(result) # [10, 14, 17, 19, 20, 28, 29]