Python归并排序实现：为何结果空列表需定义在递归后、while循环前

归并排序是通过分治递归实现的，每一次调用mergeSort处理任意长度的子数组时，都会生成一个独立的函数栈帧，栈帧里定义的所有局部变量都是当前调用独有的，不会和其他层级的递归调用共享。

两种写法的差异本质 #

1. result = []放在函数最开头的问题 #

这种写法下，所有层级的递归调用（包括递归终止的叶子节点）都会执行result = []这行代码。
归并排序的递归终止逻辑是：当子数组长度<=1时，直接返回这个子数组本身。但在函数开头就初始化result，很容易出现变量用途和初始化时机不匹配的问题：

• 如果终止条件不小心返回了result而不是当前子数组arr，那么所有上层递归拿到的左右分组group1、group2都会是空列表，后续合并的三个while循环根本没有可遍历的元素，自然看起来append操作完全没生效。
• 就算终止条件正确返回arr，这种写法也属于冗余初始化：叶子节点的栈帧永远用不到result，白创建空列表浪费内存，虽然不影响功能，但不符合按需初始化的逻辑。

2. result = []放在递归调用后、合并循环前的合理性 #

这种写法下，result的初始化时机完全匹配它的用途：
只有当当前层级的递归已经拿到了左右两个排好序的分组group1、group2，确定需要执行合并操作的时候，才会创建用来存储合并结果的空列表。
而递归终止的叶子节点（长度<=1的子数组），会直接命中终止条件返回arr，根本不会走到定义result的这行代码，既不会出现错误返回空列表的问题，也不会浪费多余内存。

举个直观的执行对比（输入数组为[3,1]）：

错误写法流程

1. 最外层调用mergeSort([3,1])，首先初始化result = []，判断长度>1，进入递归
2. 调用mergeSort([3])，这个栈帧首先也初始化result = []，如果命中终止条件时返回result，就会返回空列表
3. 调用mergeSort([1])同理，返回空列表
4. 回到最外层合并环节，发现group1=[]、group2=[]，三个while循环都不执行，最终返回空的result

正确写法流程

1. 最外层调用mergeSort([3,1])，判断长度>1，进入递归
2. 调用mergeSort([3])，直接命中终止条件，返回原数组[3]，全程不会创建result
3. 调用mergeSort([1])同理，返回原数组[1]
4. 回到最外层，此时才初始化result = []，两个分组都有实际元素，合并循环正常执行append，最终返回正确的排序列表[1,3]

补充说明：如果终止条件确实正确返回了原数组arr，那么把result放在函数开头只会多创建无用的空列表，不会影响运行结果；你遇到的append无法执行的问题，核心是两种写法的初始化时机差异，导致递归终止返回的分组不符合预期。

内容的提问来源于stack exchange，提问作者Ian