STL __merge_without_buffer算法？

在哪里可以获得__merge_without_buffer()C++ STL中使用的算法的高级描述？我正在尝试使用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.

How do we choose a pivot? In the implementation I'm looking at, it chooses the median element from the larger subrange (i.e. if [first, middle) has more elements than [middle, last), it chooses the median of [first, middle); otherwise, it chooses the median of [middle, last)). Since the subranges are already sorted, choosing the median is trivial. This pivot choice ensures that when recursively merging the two subranges, each subproblem is no more than 3/4 the size of the current problem, because in the worst case, at least 1/4 of the elements are larger than or smaller than the pivot.

这是什么运行时间？该std::rotate()调用需要O(N)时间,我们对自己进行两次递归调用.这相当于O(N log N)的运行时间.但请注意,这只是mergesort中的一个步骤:请记住,在mergesort中,您首先递归地对两半进行排序,然后进行合并.因此,mergesort的运行时间的递归关系现在是:

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

将其插入Master定理中,您现在可以在O(N log ² N)时间内运行mergesort !

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

到位

稳定

在O(N log N)时间内运行

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