比較で並べ替える限界 — 下限があるということ

上限の側は cppreference の std::sort の Complexity 欄から読めます。

Given N as last - first: 1,3) 𝓞(N·log(N)) comparisons using operator< (until C++20) std::less{} (since C++20).

これは下限ではありません。 𝓞 記法は上界なので、「実装はこれ以下の比較回数で済ませよ」という要求です。「std::sort が n log n だからソートは n log n が限界」は逆向きの読みです。限界(下限)は前節の情報理論の側から来ます。

同じページの Notes に、その要求が後から強くなった経緯があります。

Before LWG713, the complexity requirement allowed sort() to be implemented using only Quicksort, which may need 𝓞(N²) comparisons in the worst case.

ページ下部の Defect reports の表が LWG 713 の変更を対で記録します。修正前が the 𝓞(N·log(N)) time complexity was only required on the average、修正後が it is required for the worst case。

かつては平均でしか要求されていなかったわけです。「平均か最悪か」を添える理由が、この記録に残っています。

安定版も見ます。std::stable_sort の Complexity 欄。

1,3) 𝓞(N·log²(N)) comparisons using operator< (until C++20) std::less{} (since C++20) (or only 𝓞(N·log(N)) comparisons if enough extra memory is available).

括弧の中を落としてはいけません。 追加メモリが十分あれば 𝓞(N·log(N)) です。Notes によれば一時バッファの確保を試み、失敗したときだけ効率の落ちる方が選ばれます。

listsort.txt には比較回数の実測表が載っています。列の記号は直感と逆に見えるので、定義から引きます。

*sort: random data \sort: descending data /sort: ascending data =sort: all equal

n=32,768 での TimSort の比較回数です。

入力の条件          比較回数     lg(n!) との関係
*sort(ランダム)     448,885     下限 444,255 のすぐ上
\sort(降順)          32,767     n-1。下限を大きく下回る
/sort(昇順)          32,767     n-1
=sort(全て同じ)      32,767     n-1

ランダムな入力では 448,885 回。 lg(32768!) = 444,255 なので、下限の約1.01倍です。下限のすぐ上に張り付いている——これが「上限と下限が一致する」ことの実物です。

一方、昇順・降順・全同値では 32,767 = n-1 回。降順でも n-1 で済むのは、TimSort が降順の連(run)を見つけて反転するためです。

なお、下限の値そのものを見ておきます。n=100万で計算すると、lg(n!) は約 1,849万、n·log₂n は約 1,993万 です。漸近的に等しいというのは「比が1に近づく」という意味であって、この規模では約8%違います。「lg(n!) は漸近的に n log n に等しい」と一段挟まずに置き換えると、数字が合わなくなります。