Python 归并排序实现详解与核心代码

归并排序的核心逻辑

归并排序（MERGE-SORT）建立在归并操作上，核心遵循分治（Divide-and-Conquer）原则。它将原问题划分为规模更小的子问题独立求解，随后将结果拼接合并。具体到数据排序时，先将无序列表切分为极小的有序片段，再通过两两对比的方式将这些片段重新组合，最终形成完整的有序序列。

算法执行步骤拆解

整个流程可严格划分为三个连续阶段：

第1步：划分区间（分解）

目的：将待排序序列缩小至可独立处理的粒度。
入口：接收任意长度的列表或数组对象。
动作：计算中点索引 mid = len(arr) // 2，使用切片语法生成左半区 L = arr[:mid] 与右半区 R = arr[mid:]。
重要参数：整除运算符 // 确保索引始终为整数。
完成状态：原始数组被准确切割为两个新列表，当子列表长度等于 1 时触发基线条件，停止进一步分割。

第2步：递归排序子区间

目的：确保左右两部分各自内部保持升序排列，为后续合并奠定基础。
入口：上一步生成的 L 和 R。
动作：对两个子列表再次调用本函数，利用调用栈逐层深入直至最底层单元素节点，随后在回溯阶段进入合并环节。
完成状态：左右分区均转化为已排序数组，递归栈展开完毕，控制权回归至当前层级的合并逻辑。

第3步：双指针合并有序段

目的：将两段有序数据融合为单一有序序列，保证元素不丢失且相对位置稳定。
入口：已排序的 L、R 以及用于存放结果的原始数组容器。
动作：初始化索引指针 i = j = k = 0。执行循环 while i < len(L) and j < len(R)，每次比对 L[i] 与 R[j]，将较小值赋给 arr[k] 并推进对应左侧或右侧指针，同时主索引 k 自增。
重要参数：需处理边界溢出。循环结束后，分别使用独立 while 将未耗尽区间的剩余项直接追加到 arr 末尾，避免漏写数据。
完成状态：当前层级的合并闭环完成，k 达到当前区间总长度，向上返回层级继续执行相同逻辑。

Python 代码实现与运行验证

以下为可直接复制到 Python 环境执行的完整脚本。代码严格遵循上述步骤，采用切片创建临时列表配合原地覆盖的方式实现，兼顾可读性与标准算法逻辑。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中间索引
        L = arr[:mid]  # 左半部分
        R = arr[mid:]  # 右半部分

        merge_sort(L)  # 递归地排序左半部分
        merge_sort(R)  # 递归地排序右半部分

        # 合并两个有序数组
        i = j = k = 0

        # 复制数据到临时数组L[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 复制左半部分剩余的数据
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        # 复制右半部分剩余的数据
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 测试代码
arr = [12, 11, 13, 5, 6, 7]
print("未排序的数组:", arr)
merge_sort(arr)
print("排序后的数组:", arr)

运行结果核对：脚本执行后控制台首先输出未排序的初始序列，调用 merge_sort(arr) 后再次打印，预期显示按升序排列的结果 [5, 6, 7, 11, 12, 13]。若输出顺序不符，请重点检查指针递增位置是否错位，或遗漏了尾部元素的拷贝分支。

完成判断与简要总结

验证代码无误的标准是处理包含重复值、负数或长序列的输入后，返回结果完全符合升序定义且无任何元素丢失。归并排序依靠稳定的递归拆分与精确的双指针比对保障正确性，时间复杂度恒定在 O(n log n)，适合对稳定性有要求或数据量较大的场景。以上就是 Python 归并排序原理与代码实现的详细内容，更多关于算法基础与排序技巧的资料请关注本站其它相关文章！