各値の出現回数を数え、出力位置を直接求めます。狭い範囲の整数なら、比較ソートより効率的になる場合があります。

計数ソートの集計・累積和・配置を示すシミュレーター

再生、ステップ実行、スライダーで操作できます。下段は出力配列out、右下はcount配列です。

時間計算量O(n + k)

追加領域O(n + k)

安定はい

値同士の比較ゼロ

前提条件狭い範囲の整数

累積和で位置を決める

累積和を取るとcount[v]はv以下の要素数、つまりvの出力区間の終端になります。入力を後ろから走査して区間の末尾から配置すると、同じ値の順序が保たれます。この安定性により、基数ソートの各桁の整列にも利用できます。

kは値域の大きさです。0～10億のような広い値域ではcount配列が大きくなりすぎます。

大量のデータと狭い値域

1000万個の整数が1万以下に収まる場合、全要素を保存して整列する代わりに出現回数を集計し、値の順に出力すると時間とメモリを節約できます。

import sys
input = sys.stdin.readline
cnt = [0] * 10001
for _ in range(int(input())):
    cnt[int(input())] += 1
for v in range(10001):
    if cnt[v]:
        sys.stdout.write((str(v) + '\n') * cnt[v])