Time and Space Complexity

時間計算量:

• O(n + k)
  • ここで n は要素数、k は値の範囲 (max + 1) です。カウントするために1回、再構築するためにカウント配列を1回走査します。
• k が小さく固定されている場合、これは実質的に O(n) となり、比較ソートの O(n log n) よりも高速です。

空間計算量:

• O(n + k)
  • カウント配列は O(k) を使用し、出力は O(n) を使用します。

まとめ:

• 計数ソート（Counting Sort）は、安定した非比較ソートであり、小さな整数の範囲に対して線形時間で実行されます。
• 値の範囲 k が非常に大きい場合、カウント配列が巨大になるため、適していません。このバージョンでは非負の整数を想定しています。