0〜k の範囲の整数だけからなる n 個のデータを、値ごとの出現回数を数えて整列する計数ソート（分布数え上げソート）の時間計算量はどれか。

解説

正解は「$O(n+k)$」です。計数ソートは、値ごとの出現回数を数える大きさ k+1 の配列を用意し、データを1回走査して数え（$O(n)$）、その配列を先頭から順に見て値を出力し直します（$O(n+k)$）。要素どうしを比較しないため、比較ソートの下限 $\Omega (n\log n)$ に縛られません。ただし、値の範囲 k が大きいと作業領域と時間が増えます。「$O(n\log n)$」は、マージソートなど比較に基づく効率的な整列の計算量です。「$O(nk)$」は、値ごとにデータ全体を走査し直すような非効率な実装の場合です。「$O(n^2)$」は、バブルソートなど単純な比較ソートの計算量です。