堆排序与合并排序速度

尽管时间复杂度相同，但恒定因素却不同。通常，在具有4或更大方式缓存的典型系统上，合并排序将明显更快，因为合并排序将执行两次运行的顺序读取，以及对单个合并运行的顺序写入。我记得用C编写的合并排序比用汇编编写的优化堆排序要快。

一个问题是堆排序交换数据，即每个交换两次读取和两次写入，而合并排序移动数据，每次移动一次读取和一次写入。

合并排序的主要缺点是在具有4 GB或更多RAM的PC上，需要与原始数组大小相同（或可选为原始大小的1/2）的第二个数组（或向量）来进行工作存储，这通常不是问题。

在我的系统上，英特尔3770K 3.5 GHz，Windows 7 Pro 64位，Visual Studio 2015对2 ^ 24 = 16,777,216 64位无符号整数进行排序，堆排序需要7.98秒，而自下而上的合并排序需要1.59秒，自上而下的合并排序需要1.65秒。