STL __merge_without_buffer 算法？

Question

我在哪里可以获得有关所用算法的高级描述 __merge_without_buffer() 在 C++ STL 中？我正在尝试用 D 编程语言重新实现此代码，并进行一些增强。仅通过阅读 STL 源代码，我似乎无法理解它在算法层面上所做的事情，因为有太多的低级细节掩盖了它。另外，我不想盲目地翻译代码，因为那样的话，如果它不起作用，我就不知道为什么，而且我将无法添加我的增强功能。

Answer 1

__merge_without_buffer() 正在执行一个 就地合并, ，作为就地合并排序的合并步骤。它以两个范围的数据作为输入 [first, middle) 和 [middle, last) 假设已经排序。这 len1 和 len2 参数等于两个输入范围的长度，即 (middle - first) 和 (last - middle) 分别。

首先，它选择一个 枢 元素。然后，它将数据重新排列为顺序 A1 B1 A2 B2, ， 在哪里 A1 是元素的集合 [first, middle) 小于枢轴， A2 是元素的集合 [first, middle) 大于或等于枢轴， B1 是元素的集合 [middle, last) 小于枢轴，并且 B2 是元素的集合 [middle, last) 大于或等于主元。注意数据原来是按顺序排列的 A1 A2 B1 B2, ，所以我们需要做的就是转动 A2 B1 进入 B1 A2. 。这是通过调用 std::rotate(), ，它就是这样做的。

现在我们已经分离出了小于主元的元素（A1 和 B1) 来自那些大于或等于主元 (A2 和 B2），所以现在我们可以递归地合并两个子范围 A1 A2 和 B1 B2.

我们如何选择枢轴？在我正在研究的实现中，它从较大的子范围中选择中值元素（即如果 [first, middle) 的元素多于 [middle, last), ，它选择的中位数 [first, middle);否则，它选择中位数 [middle, last)）。由于子范围已经排序，因此选择中位数很简单。这种主元选择确保了当递归合并两个子范围时，每个子问题不超过当前问题大小的 3/4，因为在最坏的情况下，至少有 1/4 的元素大于或小于主元。

这个的运行时间是多少？这 std::rotate() call 需要 O(N) 时间，并且我们对自己进行了两次递归调用。这相当于 O(N log N) 的运行时间。但是，请注意，这只是合并排序中的一个步骤：请记住，在合并排序中，您首先对两半进行递归排序，然后合并。因此，归并排序运行时间的递推关系为：

T(N) = 2T(N/2) + O(N log N)

将其插入 主定理, ，您会发现合并排序现在以 O(N log² N）时间！

作为有趣的最后一点，请考虑基于比较的排序算法的以下三个特性：

1. 到位
2. 稳定的
3. 运行时间为 O(N log N)

通常，您一次只能得到其中的 2 个 - 快速排序得到 (1) 和 (3)，归并排序得到 (2) 和 (3)，而就地归并排序得到 (1) 和 (2)。非基于比较的排序（例如计数排序）可以实现所有 3 个排序，但这些排序只能对某些数据类型进行排序。可能存在一种基于比较的排序可以实现所有这 3 个目的，但如果存在，我不知道它的存在，而且几乎可以肯定它要复杂得多。