归并排序详解：递归与归并过程

归并排序是一种高效的排序算法，其基本思想是通过分治策略将大问题分解为小问题，然后逐步解决，最后将结果合并。算法的核心在于“归并”操作，即合并两个已经排好序的子序列，形成一个更大的有序序列。在设计上，归并排序遵循递归原则，将原始数组分为左右两个子数组，直到每个子数组只有一个元素，这时可以认为是有序的，然后逐层合并。 1. 时间复杂度：归并排序在所有情况下（包括最坏、最好和平均情况）的时间复杂度都是O(nlogn)，这是因为无论数组如何划分，都需要对每个子数组进行logn次的递归调用，每次递归过程中又需要线性时间O(n)来合并两个子序列。这是其名字"归并"所暗示的，因为它将数组分割、处理和合并的过程结合起来，达到了最优的时间复杂度。 2. 递归过程：归并排序的递归函数`mergeSort`采用分治策略，首先检查数组长度是否小于等于2，如果是，则无需进一步排序，因为单个元素或空序列都是有序的。接着，定义中点`mi`，将数组分为两部分，分别对左半部分和右半部分进行递归排序。最后，调用`merge`函数合并排序好的两个子数组。 3. 归并算法：`merge`函数是归并排序的关键部分。它创建两个临时数组B和C，用于存储左右子数组，然后通过比较元素大小，将较小的元素依次放入合并后的结果数组A中。当一个子数组遍历完，就将另一个子数组剩余的部分直接添加到A中。这个过程保证了合并后的序列始终有序。 4. 二路归并：二路归并算法进一步优化了合并过程，它将两个子数组同时遍历，这样在任何时候都能找到当前最小值，从而减少了比较次数。这种实现方式效率更高，尤其是在处理大规模数据时。 5. 正确性与空间复杂度：虽然归并排序的正确性通过归纳法可证明，但需要注意的是，递归过程中会产生额外的空间，因为需要保存递归调用的信息。对于原地归并（in-place merge），即在原数组上进行归并，空间复杂度会降低，但通常采用非原地归并以保持代码简洁。 归并排序凭借其稳定的性能和清晰的逻辑，是排序算法中经典且高效的选择，尤其适合处理大量数据。理解和掌握归并排序，不仅有助于提高编程技巧，也有助于理解其他基于分治思想的算法。