algorithm - O（n * log（n））時間とO（1）空間の複雑さによる安定した比較ソート

Question

ウィキペディアの並べ替えアルゴリズムのリストを調べていると、 （最悪の場合）時間計算量と（最悪の場合）空間計算量を持つ安定した比較並べ替えがないことに気付きました。これは確かに理論上の境界のように見えますが、私はそれについてのより多くの情報を見つけることができませんでした。O(n*log(n))O(1)

これをどのように証明しますか？

O(n*log(n))注：比較ソートの最悪の場合の時間計算量の下限について知っています。

Answer 1

その記事が言っていることにもかかわらず、インプレースで安定したマージソートを行うことができO(n log n)ます。

これは、それを実装する2つの方法を説明する論文です。

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);
}