（1）遞歸寫法

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

    # 計(jì)算列表的中間位置，用于切片操作
    mid = len(lst) // 2

    # 對列表的左半部和右半部分別進(jìn)行排序
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    # 將排序后的兩個(gè)子列表合并為一個(gè)有序列表
    return merge(left, right)
    

def merge(left, right):
    """合并兩個(gè)有序子列表"""
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    # 當(dāng)任意一列表元素全部彈出，剩余元素直接追加到結(jié)果列表尾部
    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):
    """對整個(gè)表進(jìn)行一趟歸并"""
    i = 0
    # 歸并length長的兩相鄰子表
    while i+2*length-1 < n:
        merge(nums, i, i+length-1, i+2*length-1)
        i += 2*length
    # 歸并余下兩個(gè)子表，后者長度小于length
    if i+length-1 < n:
        merge(nums, i, i+length-1, len(nums)-1)

def merge(nums, low, mid, high):
    """歸并相鄰的兩個(gè)有序表
    low: 第1段的首下標(biāo)
    mid: 第1段的尾下標(biāo)
    high: 第2段的尾下標(biāo)
    """
    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]