归并排序时间复杂度疑问：合并环节为何是线性复杂度？

先纠正你列的运算量式子——你搞错了每层的总运算规模。归并排序的每一层（不管递归拆分到哪一级），所有子数组的总长度始终等于原数组长度n，所以每一层的合并总运算量其实是固定的：

• 最顶层（合并最终的两个子数组）：1个数组合并，长度n，运算量为k*n
• 上一层：2个长度为n/2的子数组，每个合并运算量是k*(n/2)，两个加起来就是k*(n/2)*2 = k*n
• 再上一层：4个长度为n/4的子数组，每个合并运算量k*(n/4)，四个加起来是k*(n/4)*4 = k*n
• ...以此类推，直到最底层（拆分到单个元素，无需合并）

这样算下来，每一层的合并总运算量都是k*n，而递归的总层数是log₂n层（因为每次拆分都是把数组分成两半，直到拆成单个元素，需要log₂n次拆分，对应log₂n层合并操作）。

总运算量就是：k*n + k*n + ... + k*n（共log₂n项）= k*n*log₂n，忽略常数k和对数底数（时间复杂度里对数底数不影响量级），就得到了**O(nlogn)**的时间复杂度。

你之前列的式子错误在于把每层的单个子数组长度当成了求和项的基数，但实际上应该看每层的总长度——不管子数组拆得多细，每层所有子数组加起来都是n，所以每层合并的总工作量是固定的O(n)，乘以层数logn就是总复杂度。

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