1、算法步骤

a. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

b. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

c. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

d. 重复步骤 c 直到某一指针达到序列尾；

e. 将另一序列剩下的所有元素直接复制到合并序列尾。

2、动图演示

3、代码

# 定义一个函数mergeSort，参数为一个列表arr
def mergeSort(arr):
    # 导入math模块
    import math
    # 如果列表长度小于2，直接返回该列表（已排序）
    if len(arr) < 2:
        return arr
    # 计算列表中间位置
    middle = math.floor(len(arr) / 2)
    # 将列表分为左右两部分
    left, right = arr[0:middle], arr[middle:]
    # 调用merge函数对左右两部分进行合并排序
    return merge(mergeSort(left), mergeSort(right))

# 定义一个函数merge，参数为两个已排序的列表left和right
def merge(left, right):
    # 初始化结果列表
    result = []
    # 循环比较left和right中的元素，并按顺序合并到结果列表中
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 将剩余元素（如果有）依次添加到结果列表中
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    # 返回合并后的结果列表
    return result

打赏 支付宝打赏 微信打赏