Motivation

カウンティングソート（Counting Sort）は、2つの要素を比較することはありません。値を直接count配列のインデックスとして使用します。これにより、線形時間での実行が可能になります。

なぜカウンティングソートを学ぶのか？

• 線形時間： O(n + k) で動作します。ここで、n は要素数、k は値の範囲です。k が小さい場合、O(n log n) よりも高速です。
• 安定（慎重に実装した場合）： 基数ソート（Radix Sort）の基礎となります。基数ソートは、カウンティングソートのパスを複数回連鎖させて行います。
• 異なるアプローチ： 要素を比較するのではなく、値を集計することによってソートします。

トレードオフ：count配列のために O(k) のメモリを必要とするため、値の範囲が非常に大きい場合（例えば、10億までの数値を数個だけソートする場合など）には適していません。