キーの形を知っていれば床をくぐれる — 比較しない整列

手順をそのまま書くとこうなります。

def counting_sort(items, k, key):
    count = [0] * (k + 1)
    for it in items:                 # 1. 数える
        count[key(it) + 1] += 1
    for v in range(k):               # 2. 累積して置き場所の先頭にする
        count[v + 1] += count[v]
    out = [None] * len(items)
    for it in items:                 # 3. 前から順に置く
        out[count[key(it)]] = it
        count[key(it)] += 1
    return out

比較演算子が呼ばれるたびに数える int のサブクラスを作り、0〜150 の乱数200個で測りました(Docker python:3.14-slim、2026-10-07。測ったのは個数を数えて値を並べ直す簡略版)。

python 3.14.7 aarch64 Linux
counting sort n=200 (ages 0..150): comparisons = 0  correct = True
builtin sorted() same input: comparisons = 1275

計数ソートは 0 回、組み込みの sorted() は 1,275 回。

この「数える → 累積 → 置く」は、MIT Digital Computer Laboratory の Report R-232(Harold H. Seward、1954年)の §2.4.6 "Internal Sorting by Floating Digital Sort" に書かれています。

the items are counted before each pass to obtain the number of storage locations required for each value of the digit on the next pass.

続く Phase I で個数を数え、Phase II で累積し、Phase III で2回目の走査をして置きます。ただし本文に "counting sort" という語はありません。 前書きは "this thesis report" と書きますが学位の種別は確かめられておらず、第2章冒頭は桁ごとの分配を "the same type of sorting as that used with punched-card sorters" と書いています。誰が最初かは、この報告からは言えません。

同じ桁の箱の中を逆順に戻す「安定でない」1回を、4回のうち1つだけ混ぜました。1,000本の乱数アドレスと2本の最小例です(上と同じ環境)。

LSD radix, all 4 passes stable: correct = True
pass 0 (bits 0-7) unstable: correct = True
pass 1 (bits 8-15) unstable: correct = True
pass 2 (bits 16-23) unstable: correct = False
pass 3 (bits 24-31) unstable: correct = False
minimal example  input: ['10.0.0.1', '10.0.0.2']
all stable         -> ['10.0.0.1', '10.0.0.2'] correct = True
last pass unstable -> ['10.0.0.2', '10.0.0.1'] correct = False

3回目・4回目を崩すと壊れ、2本だけの例でも最後の回を崩すと逆転します。 10.0.0.1 と 10.0.0.2 は最上位バイトが同じなので、最後の回で箱の中を逆にすると、それまでの順が失われます。

1回目は崩しても壊れません。 1回目より前の並びは入力の順で、守るべき情報がまだ無いからです。2回目が壊れなかったのは、この1,000本でたまたまそうだっただけで、保証ではありません。10.0.1.1 と 10.0.1.2 の2本なら、3回目を崩しても2回目を崩しても逆転します(2回目は手元の Python 3.14.6 / macOS arm64 で確認)。

実際のライブラリにもあります。NumPy v2.5 の numpy.sort 公式文書(2026-10-07 取得)の Notes です。

'mergesort' and 'stable' are mapped to radix sort for integer data types. Radix sort is an O(n) sort instead of O(n log n).

どのアルゴリズムが選ばれたかを実行時に返す API は無いので、ここはソースを読むしかありません。