[解決済み] O(n)の整数ソートアルゴリズムはあるか？

質問内容

先週、偶然にも 本紙 2ページ目で著者が言及しています。

なお、これはエッジの重みが整数の場合、線形実行時間となる。

3ページ目も同様です。

これにより、エッジの重みが整数の場合は線形実行時間、比較ベースのソートの場合はO(m log n)となる。

そして8ページ目。

特に、高速な整数ソートを使用すれば、おそらくGPAはかなり高速化されるでしょう。

これは、整数値に対して特殊な状況下でO(n)のソートアルゴリズムが存在するということでしょうか？それとも、グラフ理論の専門分野なのでしょうか？

PS:
参考文献[3]は、1ページ目に書いてあるので参考になるかもしれませんね。

整数エッジウェイト[3]、[・・・]などのグラフクラスでは、さらなる改善が達成されました。

が、科学雑誌には一切アクセスできませんでした。

解決方法は？

はい。 基数ソート と カウントソート は O(N) . これらは、比較ベースのソートではありません。 Ω(N log N) を下限とする。

正確には、Radixソートは O(kN) ここで k はソートされる値の桁数である。カウントソートは O(N + k) ここで k はソートされる数値の範囲である。

を使用する特定のアプリケーションがあります。 k が十分に小さく、ラディックスソートとカウントソートの両方が実際には線形時間性能を示す。