C++两种Merge Sort（归并排序）实现方式的性能与优劣对比

第二种传入临时temp数组的实现更优，运行速度更快，工程实践中更推荐使用，核心原因如下：

• 内存分配开销差异巨大
  第一种实现每次执行merge操作时都要调用new动态分配两个临时数组，执行完再delete释放内存。堆内存的分配和释放本身是重量级操作，需要调用操作系统内核接口、处理内存块管理逻辑，在数据规模较大、递归merge次数多的场景下，这部分开销会占据总运行时间的很大比例。而第二种实现仅在排序开始前一次性分配和原数组大小相同的临时缓冲区，全程复用这块内存，完全规避了重复的内存分配释放开销。
• 缓存访问效率更高
  第一种实现每次new出的临时数组内存地址不固定，频繁的分配释放还容易产生内存碎片，CPU访问这些离散的内存块时缓存命中率很低。第二种实现的临时数组是一整块连续的内存空间，全程复用，访问时的局部性更好，CPU缓存命中率高很多，内存访问速度优势明显。
• 可靠性更高
  第一种实现每一次new都存在分配失败的风险，若中间流程出现异常很容易出现内存泄漏问题。第二种实现仅需管理一次内存的分配和释放，出错概率低，内存管理成本更小。

可能有人会注意到第二种实现的merge函数最后多了一步将临时数组数据拷贝回原数组的循环，但这部分仅涉及连续内存的顺序拷贝，开销极小，和第一种实现反复的堆内存分配释放开销相比完全可以忽略。实际测试中，当数组长度超过1000时，第二种实现的运行速度通常是第一种的3~10倍，数组越大优势越明显。

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