52230


長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし [Wikipedia
のソートの記事](https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88)を見ると、バケットソートやバイトニックソートの平均時間計算量は
n log n を下回っているように見えます。何故でしょうか？


CC BY-SA 4.0
2019-01-23T02:54:12.133
52229
2019-01-23T11:40:52.197
2019-01-23T03:15:14.940
19110
19110
question
アルゴリズム sort 計算量
ソートに必要な最低計算量は n log n ではないのか？


バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。

比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が
Ω(n log n) になります。

それ以外の場合、Ω(n log n)
を下回ることがあります。バケットソートは配列の要素の種類が分かっていることが前提にあるため、比較ソートではありません。バイトニックソートは並列計算を使ったアルゴリズムであり、逐次のアルゴリズムではありません。


CC BY-SA 4.0
2019-01-23T02:54:12.133
52230
2019-01-23T11:40:52.197
2019-01-23T11:40:52.197
19110
19110
52229
answer