我在哪里可以获得 C++ STL 中 __merge_without_buffer() 中使用的算法的体面的高级描述？我正在尝试用 D 编程语言重新实现此代码，并进行一些增强。我似乎无法通过阅读 STL 源代码来理解它在算法级别上所做的事情，因为有太多低级细节掩盖了它。此外，我不想只是盲目地翻译代码，因为那样的话，如果它不起作用，我将不知道为什么，并且我将无法添加我的增强功能。
最佳答案
__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) 的中值)。由于子范围已经排序，选择中位数是微不足道的。这种pivot选择确保在递归合并两个子范围时，每个子问题不超过当前问题大小的3/4，因为在最坏的情况下，至少有1/4的元素大于或小于pivot .
这个的运行时间是多少？ std::rotate() 调用需要 O(N) 时间，我们对自己进行了两次递归调用。这相当于 O(N log N) 的运行时间。但是，请注意，这只是归并排序的一个步骤:请记住，在归并排序中，您首先对两半进行递归排序，然后进行合并。因此，现在归并排序运行时间的递推关系为:T(N) = 2T(N/2) + O(N log N)
将其插入 Master theorem ，您现在可以在 O(N log2 N) 时间内运行合并排序!
作为一个有趣的最后一点，请考虑基于比较的排序算法的以下三个特性:
您通常一次只能获得其中的 2 个 - 快速排序获得 (1) 和 (3)，归并排序获得 (2) 和 (3)，就地归并排序获得 (1) 和 (2)。非基于比较的排序(例如计数排序)可以实现所有 3 种排序，但这些排序只能对某些数据类型进行排序。可能存在一种基于比较的排序，它可以实现所有 3 个，但如果有，我不知道它的存在，而且几乎可以肯定它要复杂得多。
关于c++ - STL __merge_without_buffer 算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/438012/