为什么我实现的归并排序（merge sort）运行效率极低？

性能问题核心原因 #

你的归并排序时间复杂度已经从标准实现的O(nlogn) 退化到了O(n²)，性能暴跌的根源在以下几个点：

• 自定义工具方法arrAdd、arrRem的时间复杂度太高
  这两个方法每次执行都会创建新数组，再全量拷贝原有数组内容，单次操作的时间复杂度和入参数组长度正相关，为O(k)，频繁调用会产生巨量的冗余拷贝操作。
• 数组拆分逻辑冗余开销过大
  标准归并排序拆分只需要按下标划分区间即可，你的实现是循环调用arrRem删除原数组首元素来填充子数组，拆分一个长度为n的数组就要执行n次O(k)的删除操作，仅拆分步骤时间复杂度就达到了O(n²)。
• 合并阶段开销过大
  标准merge操作只需要预先创建一个长度为两个子数组长度之和的结果数组，用指针遍历两个子数组写入即可，时间复杂度为O(n)。你的实现每次新增元素都调用arrAdd，每次都要全量拷贝已有结果数组，合并步骤的时间复杂度也退化为O(n²)。

优化方案 #

1. 拆分阶段不再生成新的子数组，递归时只传递原数组、左边界下标、右边界下标，仅通过下标划分待排序的区间范围，完全避免拆分过程中的数组拷贝。
2. 合并阶段预先计算两个待合并区间的总长度，一次性创建对应大小的结果数组，用两个指针分别遍历两个待合并区间，直接往结果数组对应位置赋值，完全弃用arrAdd、arrRem方法。
3. 临时数组可以全局仅初始化一次，避免每次合并都重复申请新的数组空间，进一步降低内存操作开销。

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