algorithm - 整数が一様分布に従うと仮定して、ランダムな整数の配列をソートする最速の方法は何でしょうか?

Question

タイトルの通りです。整数は <0, 10^18> です

Answer 1

Flashsortは、既知の一様分布にあるデータを利用する並べ替えアルゴリズムですO(n)。

Answer 2

キーが常に整数である場合、基数ソートはクイックソートなどの通常の比較ベースのソートよりも効率的で、O(kN) としてスケーリングされます。ここで、N はアイテムの数、k はキーの平均長 (ビット単位) です。したがって、これはソートする整数の数に線形であり、N が十分に大きくなるとクイックソートよりも優先されます。説明と C++ 実装の例については、http://en.wikipedia.org/wiki/Radix_sortを参照してください。