並べ替えアルゴリズムに関するウィキペディアのこの記事を読むと、smoothsort が最適な並べ替えアルゴリズムであることがわかります。最高、平均、最悪のすべてのカテゴリで最高のパフォーマンスを発揮します。どのカテゴリーでもこれに勝るものはありません。また、一定のメモリ要件があります。唯一の欠点は、安定していないことです。
メモリでは timsort を上回り、最悪の場合のパフォーマンスとメモリの両方でクイックソートを上回ります。
しかし、スムーズソートについては聞いたことがありません。誰もそれについて言及したことはなく、ほとんどの議論は他のソート アルゴリズムを中心に展開しているようです。
何故ですか？
Big-O のパフォーマンスは論文の出版には最適ですが、現実の世界では定数にも注目する必要があります。クイックソートは、内部ループを非常に効率的に実装でき、非常にキャッシュフレンドリーであるため、長い間、不安定なインプレース メモリ内ソートに最適なアルゴリズムでした。スムーズソートの内部ループをクイックソートと同じくらい効率的に、またはほぼ同じくらい効率的に実装できたとしても、おそらくそのキャッシュ ミス率が遅いことに気付くでしょう。
適切なピボットを選択し (異常なケースの数を減らすため)、異常なケースを検出するためにもう少し労力を費やすことで、クイックソートの最悪のケースのパフォーマンスを軽減します。introsortを参照してください。Introsort は最初にクイックソートを実行しますが、過剰な再帰を検出するとヒープソートに切り替えます (これはクイックソートの異常なケースを示しています)。
より良い漸近線は、より良いパフォーマンスを意味するわけではありません (通常はそうであることが判明しますが)。隠し定数は数倍大きくなる可能性があり、比較的小さなサイズの配列 (実際、比較的小さな配列は任意のサイズ、10 100である可能性がある場合) では、別のアルゴリズム (同じか、最悪の漸近的複雑さを持つ) よりも遅くなる可能性があります。例。それは漸近分析です)。しかし、スムーズソートの隠し定数については何も知りません。
たとえば、 k 次統計を見つけるための O(n) ワーストケースの時間アルゴリズムがありますが、非常に複雑であるため、ほとんどの場合、O(n log n) ワーストケース バージョンの方がパフォーマンスが優れています。
また、興味深い比較があります。
…ご覧のとおり、Timsort と Smoothsort はマスタードをカットしませんでした。Smoothsort は、すべてのケースで STL ソートよりも悪いです (std:bitset を生のビット操作に置き換えたとしても)...</p>
まず、Smoothsort が有名でないわけではありません。それはユーザーの必要性に依存し、またそれを使用するかどうかはユーザーに依存します。
スムーズソートの利点は、入力がすでにある程度ソートされている場合、O(n) 時間に近づくことですが、ヒープソートは、最初のソート状態に関係なく平均 O(n log n) です。
ドキュメントから:-
Smoothsort アルゴリズムは、文字列内のすべてのヒープのサイズをメモリに保持できる必要があります。これらの値はすべて異なるため、通常、これはビット ベクトルを使用して行われます。さらに、シーケンスには最大で O(log n) 個の数値があるため、トランス二分マシン モデルを想定すると、これらのビットは O(1) マシン語でエンコードできます。