クイックソート

概要

おそらく実用上最速のソートです．ピボットの選択において左右と真ん中の中央値を使うという有名なヒューリスティックを取り入れています．また，再帰関数は使わずにスタックで頑張っています．

貼っておいて何ですが，ソート系は標準ライブラリに任せるべきです． …そう思っていたのですが一概にそうでもないそうです．少なくとも C++ では大丈夫ですが，C，D，Java (基本型)，PHP では安易にやると危険なようです (この記事を書いている時点では)．詳しくは参考文献を見てください．

計算量

$O(n \log n)$

実装

template <typename T>
void qsort(T *l, T *r) {
    struct range {
        T *l, *r;
    };
    static range s[300];
    auto partition = [](T *l, T *r) {
        r--;
        T *m = l + (r - l) / 2;
        if (*l > *m) swap(*l, *m);
        if (*l > *r) swap(*l, *r);
        if (*m > *r) swap(*m, *r);
        swap(*l, *m);
        T piv = *l;
        while (l != r) {
            while (*r >= piv && l < r) r--;
            if (l < r) *l++ = *r;
            while (*l <= piv && l < r) l++;
            if (l < r) *r-- = *l;
        }
        *l = piv;
        return l;
    };
    int sz = 0;
    s[sz++] = {l, r};
    while (sz) {
        l = s[--sz].l;
        r = s[sz].r;
        if (l == r) continue;
        T *p = partition(l, r);
        s[sz++] = {p + 1, r};
        s[sz++] = {l, p};
        if (s[sz - 1].r - s[sz - 1].l > s[sz - 2].r - s[sz - 2].l) {
            swap(s[sz - 1], s[sz - 2]);
        }
    }
}

検証

AOJ 10029 (Submission)