[解決済み] リンクリストのソートで最も高速なアルゴリズムは？

質問

O(n log n)はリンクリストができる最高の値なのか気になります。

どのように解決するのですか？

でO(N log N)を超えることはできないと考えるのが妥当でしょう。 実行時間 .

しかし、面白いのは、ソートできるかどうかを調査することです インプレース , 安定的に とか、最悪の場合の挙動など。

Puttyで有名なSimon Tathamが、以下の方法を説明します。 マージソートでリンクリストをソートする . 彼は次のようなコメントで締めくくっています。

任意の自尊心あるソートアルゴリズムと同様に、これは実行時間O(N log N)を持ちます。これはマージソートであるため、最悪の場合の実行時間はまだ O(N log N) であり、病的なケースは存在しません。

補助的なストレージの要件は小さく、一定です (すなわち、ソートルーチン内のいくつかの変数)。配列とは本質的に異なるリンクリストの動作のおかげで、このマージソートの実装は、通常アルゴリズムに関連するO(N)の補助記憶コストを回避することができます。

また、単一および二重リンクリストの両方で動作するCでの実装例もあります。

Jørgen Fogh が以下で言及しているように、big-O 表記は、メモリの局所性、項目数が少ないなどの理由で、あるアルゴリズムがより良く動作する原因となるいくつかの定数要因を隠してしまうことがあります。