归并排序（merge_sort）

稳定，分解再合并，时间O(nlog^n)，空间O(n)

def merge_sorted(arr):
    """归并排序：二分数组+合并两个有序数组
        比较性：排序时元素之间需要比较，所以为比较排序
        稳定性：当左边的元素小于等于右边的元素就把左边的排前面，而原本左边的就是在前面，所以相同元素的相对顺序不变，故为稳定排序
        时间复杂度：O(nlog^n)，排序算法下界
        空间复杂度：O(n)，在合并子列时需要申请临时空间，而且空间大小随数列的大小而变化
        记忆方法：所谓归并肯定是要先分解，再合并
    Args:
        arr (List): 要进行归并排序的数组

    Returns:
        List: 排序后的arr数组
    """
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left, right = arr[:mid], arr[mid:]
    return merge(merge_sorted(left), merge_sorted(right))


def merge(left, right):
    """合并阶段

    Args:
        left (List): 已经递归二分的有序的左数组，极端情况下只有一个
        right (List): 已经递归二分的有序的右数组，极端情况下只有一个

    Returns:
        List: 合并left和right两个数组的新数组
    """
    res = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right
    return res


print(merge_sorted([1, 7, 9, 10, 3, 4, 5, 3, 4, 2, 3, 8]))

def merge_sort(l, r):
    """快速版本的归并排序（借鉴）

    Args:
        l (int): 最左区间
        r (int): 最右区间（闭而不是开）

    Returns:
        None: 排完在nums上
    """
    # 终止条件
    if l >= r:
        return 0
    # 递归划分
    m = (l + r) // 2
    merge_sort(l, m)
    merge_sort(m + 1, r)
    # 合并阶段
    i, j = l, m + 1
    # 暂存l,r之间的数组
    tmp[l : r + 1] = nums[l : r + 1]
    for k in range(l, r + 1):
        # 左数组遍历结束
        if i == m + 1:
            nums[k] = tmp[j]
            j += 1
        # 右数组遍历结束 或者 左节点小于等于右节点
        elif j == r + 1 or tmp[i] <= tmp[j]:
            nums[k] = tmp[i]
            i += 1
        # 左节点大于右节点
        else:
            nums[k] = tmp[j]
            j += 1
            # res += m - i + 1 # 统计逆序对


nums = [1, 7, 9, 10, 3, 4, 5, 3, 4, 2, 3, 8]
tmp = [0] * len(nums)
merge_sort(0, len(nums) - 1)
print(nums)