QuickMergesort —内部缓冲的力量

在鲜为人知的不稳定排序算法中，有QuickXsort系列算法，如QuickXsort中所述：Stefan Edelkamp和ArminWeiß对n log n-1.399n + o（n）进行平均比较。这个排序算法家族试图在介绍算法之前利用下面将要描述的内部缓冲技术。
内部缓冲和QuickXsort
内部缓冲是一种允许使用通常需要额外内存的算法的技术无需实际使用任何额外的内存：将算法应用于元素序列时，可以确定该算法将首先对序列的一部分进行操作，然后将另一部分用作与之交换的“缓冲区”元素，而不是将其存储在其他内存中，然后再进行检索。然后，它可以对序列的其余部分进行操作，直到完成。诸如块排序之类的算法使用内部缓冲来避免分配额外的内存。
QuickXsort是一系列旨在利用快速排序和内部缓冲的算法，如下所示：

选择枢轴并划分内存原始序列，保留两个分区A和B。
如果可能，在最大的分区上应用另一种通常需要额外内存（例如mergesort）的排序算法，然后将第二个分区用作内部缓冲区：最大的分区，它可以与B交换元素，而不是分配临时内存来存储值并在A中取回它们。
在剩余的分区上再次应用该技术，直到对原始序列进行排序为止。 br />这里的快速排序分区是一个很好的选择：对序列进行分区后，对两个半部分进行排序都会产生一个排序后的序列，因此可以使用任何排序算法，并且将未排序的分区之一用作内部缓冲区不是问题lem，因为它不应该被排序。
QuickMergesort
QuickMergesort就像对整个序列的quicksort一样应用分区，然后按以下方式应用mergesort：

只要我们有三分之一的空间，我们就使用Mergesort对分区数组的较大部分进行排序整个数组保留为临时内存，否则我们将使用Mergesort对较小的部分进行排序。

从说明中可以看出，只要较小的分区至少是排序顺序的三分之一。之所以这样，是因为mergesort需要一个缓冲区，缓冲区的大小最多为要排序的序列大小的一半（较大的分区）。三个枢纽选择中，我决定我可以使用std::nth_element代替分区步骤，始终选择一个枢轴，该枢轴将序列拆分为两个分区，两个分区的大小分别为要排序的分区大小的三分之二和三分之一。这样，它确保可以在每个步骤中对最大可能的分区执行mergesort。
为了简单起见，我们使用几乎平凡的自上而下的mergesort，当少于32个时，将切换为插入排序元素。无论如何，我们已经讨论足够多了，下面是代码：

#include <algorithm>
#include <functional>
#include <iterator>
#include <utility>

// Number of elements to sort under which we perform insertion sort
static constexpr int insertion_limit = 32;

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto insertion_sort(BidirectionalIterator first, BidirectionalIterator last,
                    Compare compare={})
    -> void
{
    if (first == last) return;

    for (BidirectionalIterator cur = std::next(first) ; cur != last ; ++cur) {
        BidirectionalIterator sift = cur;
        BidirectionalIterator sift_1 = std::prev(cur);

        // Compare first so we can avoid 2 moves for
        // an element already positioned correctly.
        if (compare(*sift, *sift_1)) {
            auto tmp = std::move(*sift);
            do {
                *sift-- = std::move(*sift_1);
            }
            while (sift != first && compare(tmp, *--sift_1));
            *sift = std::move(tmp);
        }
    }
}

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto buffered_inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
                            BidirectionalIterator last, BidirectionalIterator buffer,
                            Compare compare={})
    -> void
{
    if (middle - first <= last - middle) {
        auto buffer_end = std::swap_ranges(first, middle, buffer);
        half_inplace_merge(buffer, buffer_end,
                           middle, last,
                           first, compare);
    } else {
        auto buffer_end = std::swap_ranges(middle, last, buffer);
        using rev_iter = std::reverse_iterator<BidirectionalIterator>;
        half_inplace_merge(rev_iter(buffer_end), rev_iter(buffer),
                           rev_iter(middle), rev_iter(first), rev_iter(last),
                           std::not_fn(compare));
    }
}

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto internal_mergesort(BidirectionalIterator first, BidirectionalIterator last,
                        BidirectionalIterator buffer, Compare compare={})
    -> void
{
    if (std::distance(first, last) <= insertion_limit) {
        insertion_sort(first, last, compare);
        return;
    }

    auto middle = first + (last - first) / 2; // make sure left is smaller
    internal_mergesort(first, middle, buffer, compare);
    internal_mergesort(middle, last, buffer, compare);

    while (first != middle && not compare(*middle, *first)) {
        ++first;
    }
    if (first == middle) return;

    buffered_inplace_merge(first, middle, last, buffer, compare);
}

template<
    typename RandomAccessIterator,
    typename Compare = std::less<>
>
auto quickmergesort(RandomAccessIterator first, RandomAccessIterator last,
                    Compare compare={})
    -> void
{
    auto size = std::distance(first, last);
    while (size > insertion_limit) {
        auto pivot = first + 2 * (size / 3) - 2;
        std::nth_element(first, pivot, last, compare);
        internal_mergesort(first, pivot, pivot, compare);

        first = pivot;
        size = std::distance(first, last);
    }
    insertion_sort(first, last, compare);
}

insertion_sort的原始版本来自Orson Peters的pdqsort。 half_inplace_merge和buffered_inplace_merge的原始版本来自libc ++的std::inplace_merge的实现。它们已针对内部缓冲进行了修改。
复杂性和性能
std::nth_element在\ $ \ mathcal {O}（n）\ $中运行，而自上而下的合并排序在\ $ \ mathcal {O}（n \ log {n}）\ $中运行。老实说，我不知道整个事情实际上是运行在\ $ \ mathcal {O}（n \ log {n}）\ $还是\ $ \ mathcal {O}（n \ log ^ {2} {n}）\ $。我会说\ $ \ mathcal {O}（n \ log {n}）\ $，但是我不确定。由于为简单起见，我选择使用自上而下的合并排序，因此该算法占用\ $ \ mathcal {O}（\ log {n}）\ $空间，但可以使用\ $ \ mathcal {O}（1 ）\ $带有自底向上的mergesort的空间。
我有一段时间没有运行基准测试了，但是该算法的运行速度几乎与libstdc ++ std::sort（至少在当时实现了introsort）一样快基准测试），但在某些情况下除外：对于真正的随机数据和只有少量不同元素的情况，它要慢一些，对于std::sort的最差分布（当它归结到heapsort时），它会更好。它的速度几乎总是堆排序的两倍。
我唯一的基准测试是在106个整数的向量上执行的。在其他情况下，它的运行时间可能会有所不同。
结论
我认为该算法非常优雅，相当快，而且不会因自身利益而太聪明，这是一个可以做的很好的例子内部缓冲而又不像块排序那样复杂。这也使我最终找到了对std::nth_element的良好用法（我对使用std::nth_element进行分区的\ $ \ mathcal {O}（n \ log {n}）\ $ quicksort的速度感到非常失望，还是很不错的：）
和往常一样，您是否认为此代码可以明显改善某些方面，无论是从编码风格，性能还是从正确性角度考虑（请注意，有些事情已经简化了）进行代码审查，例如缺少隐藏内部的名称空间）？

问题：从正在发生的情况的描述中，我认为归因于分区步骤，合并排序变得不稳定了？

@ JS1是的，我忘记提及了，但是QuickXsort算法不是稳定的排序。我会编辑的，谢谢:)

“该算法将首先对算法的一部分进行操作”是什么意思？有错字吗？

@Caridorc这意味着我可能会将该句子分成几部分来写，但最终却毫无意义，感谢您的注意。我会解决的u__u

@Caridorc说实话，我发现内部缓冲是一个非常简单的概念，但是由于某些原因，我很难用简单的单词来描述它：/

#1 楼

我意识到，自问这个问题以来，至少可以简化两件事。的half_inplace_merge。但是，尽管名字叫half_inplace_merge，它还是可能会分配额外的内存以在可能的情况下执行异地合并，因此，在调用std::inplace_merge时，有时会使用不同类型的迭代器。

但是，在我们的情况下，合并操作始终是内部的，并且交换同一集合中的元素，因此迭代器始终相同。因此，我们可以简化std::inplace_merge的签名，如下所示：

template<
    typename InputIterator,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
                        InputIterator first2, InputIterator last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    // ...
}

它似乎并没有带来任何额外的性能成本或收益，但是它使代码更简单，更简洁。。

左分区总是较小的

在libc ++的half_inplace_merge的实现中，要在序列中合并的左分区和右分区可以有任意大小，因此检查以知道哪个

为了使算法发挥最大作用，必须使分区中的分区较小。此外，还可以使用其他技巧来缩小左侧分区，使其更小，而不会影响右侧分区的大小。最后，当调用half_inplace_merge时，左分区总是小于右分区，并使检查无效。该函数可以简化如下：

template<
    typename ForwardIterator,
    typename Compare = std::less<>
>
auto buffered_inplace_merge(ForwardIterator first, ForwardIterator middle,
                            ForwardIterator last, ForwardIterator buffer,
                            Compare compare={})
    -> void
{
    auto buffer_end = std::swap_ranges(first, middle, buffer);
    half_inplace_merge(buffer, buffer_end,
                       middle, last,
                       first, compare);
}

请注意，即使整个std::inplace_merge仍需要随机变量，删除反向迭代器也会降低函数对迭代器的要求buffered_inplace_merge导致可访问的迭代器。

删除quick_merge_sort也意味着该代码不再使用任何C ++ 17功能，并且可以与C ++ 14编译器一起使用。当然，它甚至可以与C ++ 03一起使用，但这不是重点：)

在对std::nth_element进行排序时避免不必要的小麻烦，尽管如此/>如果我们尝试用std::not_fn对std::deque进行排序，则以下行可能会执行一些额外的操作：等效于以下代码：

auto pivot = first + 2 * (size / 3) - 2;

当std::deque是quickmergesort迭代器时，首先将其递增operator+，然后递减first。考虑到std::deque和first + 2 * (size / 3)对于2迭代器而言并非微不足道，因此计算operator+然后递增operator-可能更有效。因此，通过将语句转换为以下内容，我们可以避免这种小小的不必要的悲观化：

确保我们避免这种悲观化时，使用std::deque（以及其他具有非平凡逻辑的随机访问容器）的速度显着提高。

编程黑洞网

QuickMergesort —内部缓冲的力量

评论

#1 楼