これはなに

Merge Insertion Sort を実装してみた記事です。

参考にしたのは The Art of Computer Programming Volume 3 です

Merge Insertion Sort is 何

最悪比較回数がそれなりに少なくて済むソートです

ざっくりと、

2 つずつペアにして大きいほうだけで再帰
小さいほうを挿入すべき場所をにぶたんで決める

形でソートします

小さいほうを入れていく順番が大事で、だいたいペアの大きいほうが小さいほうから入れていきます全部小さいほうから入れていくと入れる場所の候補が $1,3,5,7,9,11,13\dotsc$ 個になっていくんですけど、この順番を適切にすると最悪でも $1,4,4,8,8,16,16,\dotsc$ 個のようにできて、うれしいという感じです（入れる場所の候補が $5$ 通りや $9$ 通りあるところから選ぶと最悪比較回数が $3$ 回や $4$ 回になってしまうんですけど、そういうのを回避するように動いてがんばります）

どこかでにぶたんの分割を中央じゃないようにしたほうがよいと聞いたのでしているんですけど、どこで聞いたか忘れました（1.5 年前なので（？））お気持ち的には、にぶたんの結果が前のほうであればあるほど後の挿入の候補が増えるので、前のほうのにぶたん回数を減らしたいという感じだと思います（たぶん（1.5 年前なので（？）））

実装

$\Theta(N ^ 2)$ くらいかけてます挿入パートでぽかぽか BBST を使ってうまくすることで $O(N\operatorname{polylog}N)$ くらいにできそうだと思ってるんですけど、そう思い続けて記事が 1.5 年出なかったのでこのまま公開しますぽかか

pokalib::fill は C++20 では std::bit_ceil になりましたよね当時は C++20 がなかったので自分で実装していました

namespace pokalib{
    template<typename T>
    T fill(T x){
        --x;
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        x |= x >> 32;
        return ++x;
    }

    template<typename RandomAccessIterator, typename Comp = std::less<>>
    [[maybe_unused]] std::vector<unsigned long> merge_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Comp cmp){

        const auto N{last - first};

        std::vector<unsigned long> ret(N);
        std::iota(std::begin(ret), std::end(ret), 0UL);

        if(N == 1)return ret;

        for(unsigned long i{}, j((N + 1) / 2); j < N; ++i, ++j)if(!cmp(first[i], first[j])){
                std::swap(first[i], first[j]);
                std::swap(ret[i], ret[j]);
            }

        if(N == 2)return ret;

        {
            auto permutation{merge_insertion_sort(first + (N + 1) / 2, last, cmp)};

            std::vector<unsigned long> inv(N / 2);
            std::iota(std::begin(inv), std::end(inv), 0UL);
            std::vector<unsigned long> p(N / 2);
            std::iota(std::begin(p), std::end(p), 0UL);

            for(unsigned long i{}; i < N / 2; ++i){
                const auto j{inv[permutation[i]]};
                if(i != j){
                    std::swap(first[i], first[j]);
                    std::swap(ret[i], ret[j]);
                    std::swap(ret[i + (N + 1) / 2], ret[j + (N + 1) / 2]);
                    std::swap(p[i], p[j]);
                    std::swap(inv[p[i]], inv[p[j]]);
                }
            }
        }

        std::vector<unsigned long> inv(N + 1);
        std::iota(std::begin(inv), std::end(inv), 0UL);
        std::vector<unsigned long> p(N + 1);
        std::iota(std::begin(p), std::end(p), 0UL);

        const auto swap{[&first, &ret, &inv, &p](unsigned long x, unsigned long y){
            if(x == y)return;
            std::swap(first[x], first[y]);
            std::swap(ret[x], ret[y]);
            std::swap(p[x], p[y]);
            std::swap(inv[p[x]], inv[p[y]]);
        }};
        const auto rotate{[&swap](unsigned long L, unsigned long R){
            for(unsigned long i{R}; --i > L; )swap(L, i);
        }};
        const auto right_heavy_binary_search{[&first, &cmp, &rotate](unsigned long X, unsigned long L, unsigned long R){
            while(L + 1 < R){
                unsigned long x{R - L};
                unsigned long y{fill(x)};
                unsigned long z{3 * y / 4};
                unsigned long M{L + (x < z ? y / 4 : x - y / 2)};
                (cmp(first[M], first[X]) ? L : R) = M;
            }
            rotate(X, R);
        }};
        rotate(0, (N + 1) / 2);
        unsigned long L{1}, R{std::min<unsigned long>(3, (N + 1) / 2)}, C{8}, now{1};
        while(L < (N + 1) / 2){
            for(unsigned long i{R}; i-- > L; ++now)right_heavy_binary_search(i - L, (N + 1) / 2 - now - 1, inv[i + (N + 1) / 2]);
            C *= 2;
            L = R;
            R = std::min<decltype(R)>((C + 1) / 3, (N + 1) / 2);
        }

        return ret;
    }

    template<typename RandomAccessIterator, typename Comp = std::less<>>
    void sort_less_compare(RandomAccessIterator first, RandomAccessIterator last, Comp cmp){
        merge_insertion_sort(first, last, cmp);
    }
}

verify

ARC179 C です

atcoder.jp

practice contest B でも AC しました（終わってないので URL が出せませんぽか）

おわりに

2022 年当時に論文を漁った記憶によるともうちょっと比較回数を抑えることができるらしいですいかがでしたか？

あとこれを使わないとクエリ回数が収まらないようなことがあったらだいたい嘘解法だと思います

競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

比較回数の少ないソートについて

これはなに

Merge Insertion Sort is 何

実装

verify

おわりに