インデックスでソートするのが効率的でしょうか

Question

効率的かもしれない新しいソートアルゴリズムを考えていましたが、それについてはあまりよく分かりません。

1）正の数だけの配列aがあるとします。
2）配列を調べ、最大の数nを見つけます。
3）サイズn + 1の新しい配列bを作成します。
4）ソートされていない配列のすべてのエントリを調べ、2番目の配列の値を、探している未ソート配列の番号のインデックスで増やします。 a [i]は現在見ている番号です）
5）aのすべての要素についてこれを実行すると、配列b（擬似コードでは、このインデックスの正確な数を各インデックスに格納します。 （例：b [0] = 3は、初期配列aに3つのゼロがあることを意味します）
6）配列b全体をスキップし、空のフィールドをすべてスキップして、新しいリストまたは配列を作成します。

だから私は、このアルゴリズムは、最後に私たちは本当に時間がかかることになるだろうソート1を、構築するために全体の配列bを通過する必要がありますだけので、小さい数字のための非常に高速かつ効率的にできることを想像することができます。
たとえば、配列a = {1000、1}を持つ場合、最初の配列に2つの要素しかなくても、配列bの1001要素をチェックします。
しかし、私たちはほとんどO（n）の結果を得るべきですか？私はそれについてあまり確信していないので、私はあなたに尋ねている理由です。多分私は本当に重要なことを見逃しているかもしれません。
事前にお手数をおかけしていただきありがとうございます。

Answer 1

counting sortを再発見して、おめでとうございます。

これは、範囲が限定され、項目数が配列内の項目数よりも大幅に多い状況では、実際には非常に優れたソート方法です。

範囲が配列内のアイテムの数よりも多い場合は、従来のソートアルゴリズムを使用するとパフォーマンスが向上します。

この種のアルゴリズムはpseudo-polynomialと呼ばれます。

Answer 2

我々は、ほぼO（n）を取得する必要が

を引き起こすあなたはO（N + M）の結果を得るため、ときM - 最初の配列の最大数。プラス、あなたはO（M）のメモリを使います。だから、Mが小さい場合にだけセンスがあります。 counting sort