我一直在研究list ::sort（源代码）的有趣的GLibC实现，它似乎没有实现传统的合并排序算法（至少没有我以前见过的算法）。

基本上，它的作用是：

1. 创建一系列存储桶（总共64个）。
2. 删除要排序的列表的第一个元素，并将其与第一个（i=0th）存储桶合并。
3. 如果在合并之前i第th个存储桶不为空，则将i第个存储桶与第i+1个存储桶合并。
4. 重复步骤3，直到与一个空桶合并。
5. 重复步骤2和3，直到要排序的列表为空。
6. 从最小到最大，将所有剩余的非空存储桶合并在一起。

小提示：将存储桶X与存储桶合并Y将删除存储桶中的所有元素X，并将它们添加到存储桶中，Y同时保持所有内容排序。另请注意，存储桶中的元素数为0或2^i。

现在为什么比传统的合并方式要快？好吧，我不能肯定地说，但这里有几件事要想到：

• 它从不遍历列表以找到中间点，这也使算法对缓存更友好。
• 由于早期的存储桶较小且使用频率较高，因此调用merge垃圾桶的调用较少。
• 编译器能够更好地优化此实现。需要比较生成的程序集以确保这一点。

我敢肯定，实施此算法的人们已经对其进行了全面测试，因此，如果您想获得明确的答案，则可能必须在GCC邮件列表中提出。