ティムソートとクイックソートの比較

質問

Timsort (以下、Timsort) が最も速いソートアルゴリズムであるにもかかわらず、Quicksort が最も速いという話をよく耳にするのはなぜでしょうか? ウィキペディア によると) の方がずっと性能が良いように思えるのですが、なぜでしょうか? Google では、どのような種類の比較も見つからなかったようです。

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

TimSortは高度に最適化されたマージソートであり、従来のマージソートよりも安定かつ高速に動作します。

クイックソートと比較した場合、2つの利点があります。

1. ほぼソートされたデータ列（逆ソートされたデータも含む）に対して、信じられないほど高速に処理することができます。
2. 最悪の場合でもO(N*LOG(N))です。

正直なところ、1番が有利とは思いませんが、印象には残りました。

QuickSortの利点は以下の通りです。

1. QuickSortは非常にシンプルで、高度にチューニングされた実装でも、20行以内にそのPSeduoコードを書き出すことができます。
2. ほとんどの場合、QuickSortが最も高速です。
3. メモリ消費量は LOG(N) です。

現在、Java 7 SDKはtimsortと新しいクイックソートのバリエーション、すなわちDual Pivot QuickSortを実装しています。

安定したソートが必要な場合、timsortを試してみてください。