咨询：归并排序递归未触发基准条件为何引发无限循环？

首先得明确归并排序的核心递归逻辑：当要排序的子数组只有0个或1个元素时（也就是左边界l大于等于右边界u），这个子数组本身已经是有序的，根本不需要再拆分递归了。

但你写的if (mid)这个判断，完全没抓住这个核心，反而会触发无限循环：

• 比如当子数组只有1个元素时（比如l=u=2），mid=(2+2)/2=2，这时候mid是非零值，if(mid)条件成立，会继续调用merge_sort(a, 2, 2)，然后又计算出mid=2，再次进入递归……无限循环就这么来了！
• 只有当mid=0的特殊情况（比如l=0,u=0），if(mid)条件不成立会终止，但这只是巧合，大部分单元素子数组（比如l=1,u=1）都会陷入死循环。

把终止条件改成判断l < u——只有当子数组长度至少为2时，才进行拆分和递归：

void merge_sort(int a[], int l, int u) { 
    if (l < u) { // 正确的终止条件：子数组有至少2个元素才继续
        int mid = l + (u - l) / 2; // 用这个写法避免(l+u)溢出的问题
        merge_sort(a, l, mid); 
        merge_sort(a, mid + 1, u); 
        merge(a, l, mid, u); 
    } 
}

这里额外提个小优化：把(l + u)/2改成l + (u - l)/2，可以避免当l和u数值很大时触发整数溢出的问题。

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