（1）递归写法

def merge_sort(lst):
    """归并排序：分治策略"""
    # 如果列表只有一个元素，直接返回该列表
    if len(lst) <= 1:
        return lst

    # 计算列表的中间位置，用于切片操作
    mid = len(lst) // 2

    # 对列表的左半部和右半部分别进行排序
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    # 将排序后的两个子列表合并为一个有序列表
    return merge(left, right)
    

def merge(left, right):
    """合并两个有序子列表"""
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    # 当任意一列表元素全部弹出，剩余元素直接追加到结果列表尾部
    res += left
    res += right
    return res


# 示例
nums = [1, 2, 34, -1, -9, 0, 2, 13]
sorted_nums = merge_sort(nums)
print(sorted_nums)  # 输出: [-9, -1, 0, 1, 2, 2, 13, 34]

（2）非递归写法

def MergeSort(nums):
    """自底向上的二路归并算法"""
    length = 1
    while length < len(nums):
        MergePass(nums, length)
        length *= 2


def MergePass(nums, length):
    """对整个表进行一趟归并"""
    i = 0
    # 归并length长的两相邻子表
    while i+2*length-1 < n:
        merge(nums, i, i+length-1, i+2*length-1)
        i += 2*length
    # 归并余下两个子表，后者长度小于length
    if i+length-1 < n:
        merge(nums, i, i+length-1, len(nums)-1)

def merge(nums, low, mid, high):
    """归并相邻的两个有序表
    low: 第1段的首下标
    mid: 第1段的尾下标
    high: 第2段的尾下标
    """
    tmp = []
    i, j = low, mid+1
    while i <= mid and j <= high:
        if nums[i] <= nums[j]:
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1
    if i <= mid:
        tmp.extend(nums[i:mid+1])
    if j <= high:
        tmp.extend(nums[j:high+1])
    nums[low:high+1] = tmp[:]


x = [1, 2, 34, -1, -9, 0, 2, 13]
MergeSort(x)
print(x)    # [-9, -1, 0, 1, 2, 2, 13, 34]