具有O(n * log(n))时间复杂度和O(1)空间复杂度的稳定排序算法比较。

Question

当我查看维基百科的排序算法列表时，我注意到没有一个稳定的比较排序具有O(n*log(n))（最坏情况）时间复杂度和O(1)（最坏情况）空间复杂度。这肯定看起来像是一个理论上的界限，但我找不到更多关于它的信息。

如何证明这一点？

注意：我知道比较排序的最坏情况时间复杂度的下限为O(n*log(n))。

- Florian Brucker

---

最好在这里 http://cstheory.stackexchange.com/ - TimCodes.NET

@Chimoo：感谢你的提示，我之前不知道那个网站。 - Florian Brucker

Answer 1

尽管该文章声称，就地稳定的合并排序可以做到O(n log n)，但实际上这是可能实现的。 这篇论文详细阐述了两种实现方式。

- BlueRaja - Danny Pflughoeft

---

那篇论文中描述的排序算法是否真的稳定呢？我不确定，因为他们只在最后谈到稳定性，好像这是一个额外的目标（而归并排序并不一定意味着稳定，可能会写出一个不稳定的归并排序）。我还没有实现这两个算法中的任何一个，但根据图表判断，它们都不稳定（请参见大数据块顺序变化）。 - user1020786

非常抱歉，经过进一步检查，我认为第二个变量肯定可以稳定下来，尽管我仍然不确定第一个是否可以。 - user1020786

Answer 2

这是我从C语言实现 这里 转换而来的完整C++实现：

#include <algorithm>
#include <functional>

template<class It>
It rotate(It begin, It const middle, It end)
{
    typename std::iterator_traits<It>::difference_type i = 0, j;
    if (begin != middle && middle != end)
    {
        while ((i = std::distance(begin, middle)) !=
               (j = std::distance(middle, end)))
        {
            It k = middle;
            std::advance(
                k,
                std::max(
                    typename std::iterator_traits<It>::difference_type(),
                    j - i));
            std::swap_ranges(k, end, begin);
            if (i > j) { std::advance(begin, j); }
            else { std::advance(end, -i); }
        }
    }
    return std::swap_ranges(middle - i, middle, middle);
}

template<class It, class Less>
It bsearch(
    It begin, It left, It right,
    typename std::iterator_traits<It>::difference_type n,
    Less &less)
{
    while (left < right)
    {
        It const middle = left + std::distance(left, right) / 2;
        bool const b = !less(
            *(begin + (std::distance(middle, begin) + n)),
            *middle);
        (b ? left : right) = middle + b;
    }
    return left;
}

template<class It, class Less>
void merge(It const begin, It const middle, It const end, Less &less)
{
    bool naive_insertion_optimization = false;
    if (naive_insertion_optimization && std::distance(begin, end) < 0)
    {
        for (It i = middle; i != end; ++i)
        {
            for (It p = i; p != begin; --p)
            {
                if (!less(*p, *(p - 1)))
                {
                    break;
                }
                using std::iter_swap;
                iter_swap(p, p - 1);
            }
        }
    }
    else if (begin < middle && middle < end)
    {
        typename std::iterator_traits<It>::difference_type const
            half = std::distance(begin, end) / 2,
            left = std::distance(begin, middle),
            right = std::distance(middle, end);
        It const midpoint = begin + half;
        bool const b = left > right;
        It const i = bsearch(
            begin,
            b ? midpoint - right : begin,
            b ? midpoint : middle,
            half + left - 1,
            less);
        rotate(i, middle, begin + (std::distance(i, middle) + half));
        merge(begin, i, midpoint, less);
        merge(midpoint, midpoint + std::distance(i, middle), end, less);
    }
}

template<class It, class Less>
void sort(It const begin, It const end, Less &less)
{
    if (std::distance(begin, end) > 1)
    {
        It const middle = begin + std::distance(begin, end) / 2;
        sort(begin, middle, less);
        sort(middle, end, less);
        merge(begin, middle, end, less);
    }
}

template<class It>
void sort(It const begin, It const end)
{
    std::less<typename std::iterator_traits<It>::value_type> less;
    return sort(begin, end, less);
}

- user541686