合并排序时间复杂度推导

合并排序是一种高效的分治算法，其时间复杂度可以通过递归分析得出。下面是合并排序的主要步骤和时间复杂度推导：

1. **划分（Divide）**: 合并排序首先将数组分为两半，这一步的时间复杂度是 O(n)，因为需要遍历整个数组一次。

2. **排序（Sort）**: 对每个子数组进行排序。这是一个递归过程，直到子数组只剩下一个元素，这一步的时间复杂度也是 O(n)，因为每个子数组都会被单独处理。

3. **合并（Combine）**: 当子数组只剩一个元素时，它们已经是有序的。然后将两个子数组合并成一个有序的大数组。这个过程需要线性时间，对于两个子数组，合并操作的时间复杂度为 O(n)。

由于合并排序是递归执行的，每次划分都将问题规模减半，所以总的时间复杂度可以通过等比数列求和得到。对于每个子数组，我们需要合并两个已排序的数组，所以合并操作总共要做 log_2(n) 次。因此，总的合并操作次数是 n * log_2(n)。

所以，合并排序的平均时间复杂度和最坏时间复杂度都是 O(n log_2 n)，这是因为不论输入数据如何分布，最终都需要进行相同数量的比较和移动操作。