O（n）の記憶空間を与えられた範囲{1,2、... n^2}のn個の要素をどれくらい早くソートできますか？

私はカウントソートの使用について考えています。しかし、kはこの場合はn^2なので、それは答えだとは思わない。ソート時間はO（n + n^2）となります。また、私はそれがストレージの制限を超えてしまうと思います。O（n）の記憶空間を与えられた範囲{1,2、... n^2}のn個の要素をどれくらい早くソートできますか？

アイデア？

ありがとうございました。

2011-12-31 spider

@を参照します（[クイックソート]を見てとっていますhttp://en.wikipedia.org/wiki/Quicksort）？ – Makoto

@Makoto：クイックソートのピボットが悪いときは、実行時間はO（n^2）になります。さらに、私はO（n）の記憶空間を与えられているので、いくらかのスペースを必要とするソートアルゴリズムを使うことができると思います。 – spider

多分私は誤解していますが、これは2桁の基数nの基数ソートなので、O（n）のように見えます。 [i]％nの最初のパスのバケット、[i]/nの2番目のパスのバケット。これにはO（n）補助記憶装置が必要です。 –

bottom-up merge sortを使用すると、O（n log n）で実行され、余分なスペースを必要としません（インプレース状態であるため）。

2011-12-31 00:48:40

うーん、 – BlackBear

Merge Sortのわずかに変更されたバージョンを使用すると、リストを半分でなくn個の部分に分割することができます。マージソートの時間の複雑さはO（n log n）ですが、編集されたバージョンを取得する方法はわかりません。
誰かが私を助けている場合、私は私の答えに追加します:)

EDIT：
誰かがすでにこれを発明したと思われる、JSPerfUnkn0wnの答え

2011-12-31 00:51:37 BlackBear

答えて