稳定分区并获得O(nlogn)交换

在 en.cppreference.com 我们看到了 std::stable_partition 如果允许我们使用额外的内存,就执行O(N)交换。我能看到这个。每次我们在谓词为假的范围内找到一个元素时,我们都会将其交换到另一个缓冲区中。最后,我们可以将这个额外的缓冲区复制到成功部分的末尾。[我也假设,在这种情况下, stable_partition 只能用前向迭代器实现]

我不明白的是,林克说 稳定分区 如果不允许使用额外的内存,最多执行O(nlogn)交换。这是我的尝试。

#include <utility>

namespace cho {

    template <typename BidirIt, typename Pred>
    BidirIt stable_partition(BidirIt begin, BidirIt end, Pred p) {
        BidirIt next_p = begin;
        for(BidirIt it = begin; it != end; ++it) {
            if(it == begin && p(*it)) {
                next_p++;
                continue;
            }
            if(p(*it)) {
                std::swap(*next_p++, *it);

                // riplle back swapped element to keep stability
                BidirIt cur = it;
                do {
                    BidirIt prev = --cur; cur++;
                    std::swap(*cur--, *prev--);
                } while(cur != next_p);
            }
        }
        return next_p;
    }

    template <typename ForwardIt, typename Pred>
    ForwardIt partition(ForwardIt begin, ForwardIt end, Pred p) {
        ForwardIt next_p = begin;
        for(ForwardIt it = begin; it != end; ++it) {
            if(p(*it)) {
                std::swap(*next_p++, *it);
            }
        }
        return next_p;
    }
} 

在这种情况下,我会在交换之后进行回击。所以,如果两个连续的真实情况之间的距离是 k ,我会表演 K 交换。我认为对我的算法来说,最坏的情况发生在范围被反向分区的时候。如果有的话 p 谓词为假且 n-p 谓词为真的项,我将得到O((n-p)*p)交换。我想了想,我不知道我怎么能得到最坏的情况。

我检查了llvm中的实现,但无法真正了解如何实现O(nlogn)交换。

附:我的实现可能是错误的。我用几个输入来测试它,但就是这样。