Home > libalgo > マージソート

マージソート

概要

高速な安定ソートです.静的に大きめの作業領域を確保しています.詳しい説明はそこら中にあるのでググってください.

計算量

$\Theta(n \log n)$

実装

template <typename T>
void mergesort(T *l, T *r) {
    int n = r - l;
    static T tmp[1000010];
    auto merge = [](T *l1, T *r1, T *l2, T *r2, T *dst) {
        while (l1 != r1 && l2 != r2) {
            if (*l1 < *l2)
                *dst++ = *l1++;
            else
                *dst++ = *l2++;
        }
        while (l1 != r1) *dst++ = *l1++;
        while (l2 != r2) *dst++ = *l2++;
    };
    for (int w = 2; w / 2 < n; w <<= 1) {
        for (int i = 0; i < n; i += w) {
            merge(l + i, min(l + i + w / 2, l + n), min(l + i + w / 2, l + n),
                  min(l + i + w, l + n), tmp + i);
        }
        for (int i = 0; i < n; i++) l[i] = tmp[i];
    }
}

検証

AOJ 10029 (Submission)