最悪の入力を、乱数の側へ移す — 乱択と期待値

Java の Arrays.sort(int[])(JDK 25 の Javadoc、2026-10-07 取得)はこう書きます。

Implementation Note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.

on all data sets ——どの入力でも、と書いています。では最悪の入力はどうしたのか。ソース(タグ jdk-25-ga の DualPivotQuicksort.java)を読むと、分割の途中にこうあります。

            /*
             * Switch to heap sort if execution
             * time is becoming quadratic.
             */
            if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
                heapSort(a, low, high);
                return;
            }

再帰が深くなりすぎたら、ヒープソート(別の整列法)に切り替えます。 Javadoc の一文からは、どの仕組みが最悪を防いでいるかは分かりません。ソースを読むと、深さを数えて別の手法へ逃げる仕組みが見えます。乱数とは別の防ぎ方です。

Go は 1.19 のリリースノートでこう書きました。

The sorting algorithm has been rewritten to use pattern-defeating quicksort, which is faster for several common scenarios.

pdqsort という綴りはリリースノートには無く、ソース src/sort/zsortfunc.go のコメント「pattern-defeating quicksort(pdqsort)」にあります。そして利用者向けの pkg.go.dev/sort の本文は、手法名を一切書きません。

It makes one call to data.Len to determine n and O(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.

約束は呼び出し回数だけで、安定であることは保証しない。 中身の手法は約束の外です。

① 乱択 pivot。 同じ実験で、種を0〜99の100通りに変えて平均しました。

2 n ln n = 6214.6
exact expectation 2(n+1)H_n - 4n = 4806.4  (H_n = 6.7928)
random pivot, sorted   n=500: mean over 100 seeds=4847.1  min=4211 max=6030  mean/(2 n ln n)=0.780
random pivot, shuffled n=500: mean over 100 seeds=4756.8  min=4263 max=5744  mean/(2 n ln n)=0.765

ソート済みでも 4,847、シャッフルでも 4,757。 入力を変えても分布がほぼ同じです。先頭 pivot の 124,750 と比べると約26分の1です。

よく「期待値は約 2n ln n」と書かれますが、n=500 では 2n ln n = 6,215 で、実測はその 0.78 倍です。2n ln n は n が大きいときの先頭項で、小さい n では落とした項が効きます。正確な期待値 2(n+1)H_n − 4n(H_n は 1 + 1/2 + … + 1/n)は 4,806 で、実測とよく合います。

② ハッシュの種。 第11期で見たとおり、ハッシュ表は全部の鍵が同じバケットに入ると線形に劣化します。ハッシュ関数が固定なら、衝突する鍵の組を前もって作れます。Python の公式ドキュメント(-R の項)はこう書きます。

Hash randomization is intended to provide protection against a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict construction, O(n²) complexity.

種は起動ごとに乱数で決まります。

Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

PYTHONHASHSEED に整数を入れると種は固定され、0 なら乱数化が無効になります。目的は「to allow repeatable hashing」と書かれています。SipHash 系の関数は PEP 456(Python 3.4)が「This PEP proposes SipHash as default string and bytes hash algorithm」として導入しました(その後の既定の版は変わっています)。