归并排序 描述 归并排序是一种基于分治策略的排序算法。它将数组递归地分成两半，分别对左右两部分排序，然后将两个有序数组合并成一个有序数组。归并排序的时间复杂度为 O(n log n)，且是稳定排序算法。 分治思想 分解 ：将当前数组从中间位置分成左右两个子数组。 解决 ：递归地对左右子数组进行归并排序（直到子数组长度为1，自然有序）。 合并 ：将两个有序子数组合并为一个有序数组。 合并过程详解 合并是归并排序的核心步骤，需保证合并后的数组有序。具体流程如下： 创建临时数组存放合并结果，并初始化左右子数组的起始索引（例如 leftIndex 和 rightIndex ）。 比较左右子数组当前指向的元素，将较小者放入临时数组，并移动对应索引。 若某一子数组元素已全部合并，则将另一子数组剩余元素直接追加到临时数组末尾。 将临时数组复制回原数组对应位置。 示例演示 以数组 [38, 27, 43, 3, 9, 82, 10] 为例： 分解 ： 第一层：分成 [38, 27, 43, 3] 和 [9, 82, 10] 。 第二层：左半部分再分成 [38, 27] 和 [43, 3] ，右半部分分成 [9, 82] 和 [10] 。 继续分解直到每个子数组长度为1。 合并与排序 （从最底层开始）： 合并 [38] 和 [27] ：比较后得到 [27, 38] 。 合并 [43] 和 [3] ：得到 [3, 43] 。 合并 [27, 38] 和 [3, 43] ： 比较 27 和 3 → 放入 3；比较 27 和 43 → 放入 27；比较 38 和 43 → 放入 38；剩余 43 放入。结果： [3, 27, 38, 43] 。 右半部分同理，最终合并左右两大块得到完整有序数组。 算法实现要点 递归基线 ：当子数组长度 ≤1 时直接返回。 空间复杂度 ：合并需 O(n) 临时空间，但可优化为全局分配一次避免重复申请。 稳定性 ：合并时相等元素优先取左子数组元素，可保持原有顺序。 总结 归并排序通过分治思想将问题规模缩小，再通过合并操作解决子问题。其时间复杂度稳定为 O(n log n)，但需要额外空间，适用于数据量大且对稳定性有要求的场景（如外部排序）。