归并排序的核心逻辑是基于**分治法**的思想，将一个大问题分解为若干个相同结构的小问题来解决

归并排序的核心逻辑是基于分治法的思想，将一个大问题分解为若干个相同结构的小问题来解决。具体流程如下：

1. 分解阶段：将待排序数组不断二分，直到每个子数组只包含一个元素（单个元素天然有序）；
2. 合并阶段：通过Merge函数将两个有序的子数组合并成一个新的有序数组；
3. 递归回溯：随着递归返回，较小的有序段被逐步合并为更大的有序段，最终形成整个有序数组。

核心操作：Merge函数（以两路归并为例）

defmerge(arr,left,mid,right):# 创建临时数组存储左右两部分left_arr=arr[left:mid+1]right_arr=arr[mid+1:right+1]i=j=0# 左右子数组的指针k=left# 原数组中的位置# 按升序将元素复制回原数组whilei<len(left_arr)andj<len(right_arr):ifleft_arr[i]<=right_arr[j]:arr[k]=left_arr[i]i+=1else:arr[k]=right_arr[j]j+=1k+=1# 复制剩余元素whilei<len(left_arr):arr[k]=left_arr[i]i+=1k+=1whilej<len(right_arr):arr[k]=right_arr[j]j+=1k+=1

递归实现：MSort函数

defmsort(arr,left,right):ifleft<right:mid=(left+right)//2msort(arr,left,mid)# 递归排序左半部分msort(arr,mid+1,right)# 递归排序右半部分merge(arr,left,mid,right)# 合并已排序的两部分

归并排序性能分析

• 时间复杂度：始终为 $ O(n \log n) $，无论最好、最坏或平均情况；
• 空间复杂度：$ O(n) $，需要额外的辅助空间用于合并过程；
• 稳定性：稳定排序算法（相等元素的相对位置不会改变）；
• 是否原地：非原地排序（需要额外内存）；
• 适用场景：适合对稳定性有要求且数据量较大的排序任务，如外部排序。
• 非递归版本的归并排序（也称自底向上的归并排序）不使用递归来分解数组，而是从最小粒度（长度为1的子数组）开始，逐步合并成更大的有序段，直到整个数组有序。

实现思路：

1. 初始时，将每个元素看作一个长度为1的有序子数组；
2. 每次将相邻的两个有序子数组进行两路归并，形成长度为2、4、8……的有序段；
3. 使用循环控制当前要合并的子数组长度（size），每次翻倍；
4. 在每一趟中遍历整个数组，对每一对相邻子数组调用merge函数合并。

Python代码实现（非递归归并排序）

defmerge(arr,left,mid,right):# 辅助函数：合并 arr[left..mid] 和 arr[mid+1..right]temp=[]i,j=left,mid+1# 双指针合并两个有序部分whilei<=midandj<=right:ifarr[i]<=arr[j]:temp.append(arr[i])i+=1else:temp.append(arr[j])j+=1# 复制剩余元素whilei<=mid:temp.append(arr[i])i+=1whilej<=right:temp.append(arr[j])j+=1# 回写到原数组foridx,valinenumerate(temp):arr[left+idx]=valdefmerge_sort_iterative(arr):n=len(arr)size=1# 当前子数组的长度（从1开始，逐步翻倍）whilesize<n:# 对每一对长度为 size 的子数组进行合并forleftinrange(0,n,2*size):mid=min(left+size-1,n-1)right=min(left+2*size-1,n-1)# 如果 mid < right，说明有两个子数组可以合并ifmid<right:merge(arr,left,mid,right)size*=2# 子数组长度翻倍

示例演示：

data=[38,27,43,3,9,82,10]merge_sort_iterative(data)print(data)# 输出: [3, 9, 10, 27, 38, 43, 82]

特点分析：

• 无需递归栈：避免了递归带来的函数调用开销和栈溢出风险；
• 时间复杂度：仍为 $ O(n \log n) $，共需 $ \lceil \log_2 n \rceil $ 趟归并，每趟耗时 $ O(n) $；
• 空间复杂度：$ O(n) $，用于临时数组；
• 适用场景：适合栈空间受限或需要完全可控迭代过程的系统中。