算法七：归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。

"""
以下为merge_sort的执行过程

merge_sort(li, 0 ,8):
    merge_sort(li, 0, 4)
        merge_sort(li, 0, 2)
            merge_sort(li, 0, 1)
                 merge_sort(li, 0, 0)       #输出None
                 merge_sort(li, 1, 1)       #输出None
                 merge(li, 0, 1, 1)         #输出排序后的列表中li[0]~li[1]
            merge_sort(li, 2, 2)            #输出None
            merge(li, 0, 1, 2)              #输出排序后的列表中li[0]~li[2]
        merge_sort(li, 3, 4)
            merge_sort(li, 3, 3)            #输出None
            merge_sort(li, 4, 4)            #输出None
            merge(li, 3, 3, 4)              #输出排序后的列表li[3]~li[4]
        merge(li, 0, 2, 4)                  #输出排序后的列表li[0]~li[4]

    merge_sort(li, 5, 8)
        merge_sort(li, 5, 6)
            merge_sort(li, 5, 5)            #输出None
            merge_sort(li, 6, 6)            #输出None
            merge(li, 5, 5, 6)              #输出排序后的列表li[5]~li[6]
        merge_sort(li, 7, 8)
            merge_sort(li, 7, 7)            #输出None
            merge_sort(li, 8, 8)            #输出None
            merge(li, 7, 7, 8)              #输出排序后的列表li[7]~li[8]
        merge(li, 5, 6, 8)                  #输出排序后的列表li[5]~li[8]
    merge(li, 0, 4, 8)                      #输出排序后的列表li[0]~li[8]
"""
import random


def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltemp = []
    while i <= mid and j <= high:  # 只要左右两边都有数
        if li[i] < li[j]:
            ltemp.append(li[i])
            i += 1
        else:
            ltemp.append(li[j])
            j += 1
    # while执行完后，肯定有一部分没有数了
    while i <= mid:
        ltemp.append(li[i])
        i += 1
    while j <= high:
        ltemp.append(li[j])
        j += 1
    li[low: high+1] = ltemp


def merge_sort(li, low, high):
    if low < high: # 至少有两个元素，递归
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)

时间复杂度：O(nlogn)
空间复杂度：O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序
稳定性：归并排序是稳定的排序算法，temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变。