C++ std::sort 实现

Question

我想知道 c++11 中 std::sort 的实现。我有一个 MPI 管理的并行代码，其中每个等级将文件中的数据读取到需要排序的 vector A 中。每个排名都会调用 std::sort 来执行此操作。

当我以大约 100 个等级运行此程序时，有时会有一个等级在对 std::sort 的调用中挂起。最终，我意识到，这不是挂起，而是需要很长时间。也就是说，一个排名的排序时间比所有其他排名的时间长约 200 倍。

起初我怀疑这是一个负载平衡问题。不，我已经彻底检查了每个等级的 A 大小是否尽可能平衡。

我得出的结论是，可能只是一个等级的初始条件为 A，例如 worst-case performance of quicksort已实现(或至少是非理想情况)。

我为什么这么想？

• 如果我更改 MPI 配置(从而扰乱每个等级 A 的内容，因为它来自读取的文件)，问题就会消失，或者可以移动到其他级别。
• 如果我将 std::sort 更改为 std::stable_sort(不再使用快速排序算法)，那么一切都很好。

但是，通过在每次迭代中选择随机枢轴点来实现快速排序似乎是最明智的。如果 std::sort 就是这种情况，那么在多次迭代中从 A 中随机选择最坏情况的值是绝对不可能的(这需要导致性能下降 200 倍)。

因此，我的观察表明 std::sort 实现了固定快速排序枢轴值(例如，始终选择数组中的第一个值，或类似的值)。这是我所看到的行为可能发生的唯一方法，并且在相同的 MPI 配置上重新运行时也能给出一致的结果(确实如此)。

我的结论正确吗？我确实设法找到了 std 源，但是 sort 函数完全不可读，并且对各种辅助函数进行了大量调用，我宁愿避免兔子洞。除此之外，我正在 HPC 系统上运行，我什至不清楚如何确定 mpicxx 到底链接到什么。我找不到任何描述算法实现的文档

Answer 1

std::sort 是特定于实现的。

自 C++11 起，常规快速排序不再是有效的实现，因为所需的复杂度从平均的 O(N log N) 变为 O (N log N)。