質問: 長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
回答: バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。 比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が Ω(n log n) になります。 それ以外の場合、Ω(n log n) を下回ることがあります。バケットソートは配列の要素の種類が分かっていることが前提にあるため、比較ソートではありません。バイトニックソートは並列計算を使ったアルゴリズムであり、逐次のアルゴリズムではありません。