整数の配列を線形時間で並べ替えることはできますか？

Question

先日、私はGoogleとMicrosoftのインターンシップのインタビューについてブログを読んでいましたが、質問の1つは線形時間で整数の配列を並べる方法でした。

私はMergesortやQuicksortのようなO（n log（n））のものを注文するのに最適な方法だと思っていましたが、わかりません。何かご意見は？

Answer 1

まあ、質問にはもう少し制約があったに違いない。たとえば、配列がほんの少しの反復数で構成されている場合、[1 3 2 6 3 1 2]を使用すると、counting sortを使用して線形時間でこれを行うことができますが、より多くのスペースが使用されます。

もう1つのアルゴリズムは、Dutch National Flagアルゴリズムで、3つの繰り返し数値を線形時間で並べ替えることができます。これ以外に、私は（無知は至福ではありません：P）私は線形時間で通常の配列をソートする方法を知っているとは思わない。

あなたがRadix sortを使用する場合でも、それはO(m * n)を取るだろうが、あなたはその約O(n)

Answer 2

O(n lg n)は、あなたがする必要はありません比較ですベース種類、のためにできる最善であると主張することができますm <<< n場合あなたがお互いを比較する方法以外のソートしているアイテムについて何かを知っている。結合されたサイズの整数のリストを並べ替えると（すなわち、各整数は最大でKで、Kはから独立しています）、より特殊な問題ですので、O(n lg n)（基数ソートなど） 。