問題タブ [smoothsort]

ほとんどの値の配列がありますが、完全にはソートされておらず、いくつかの値が置き換えられています (たとえば、100000 で 50)。最も効率的に並べ替える方法は？(ここではパフォーマンスが絶対に重要であり、O(N) よりもはるかに高速である必要があります)。

Smoothsort については知っていますが、Java の実装が見つかりません。すでに実装されているかどうか知っている人はいますか？または、スムーズソートの代わりにこのタスクに何を使用できますか?

並べ替えアルゴリズムに関するウィキペディアのこの記事を読むと、smoothsort が最適な並べ替えアルゴリズムであることがわかります。最高、平均、最悪のすべてのカテゴリで最高のパフォーマンスを発揮します。どのカテゴリーでもこれに勝るものはありません。また、一定のメモリ要件があります。唯一の欠点は、安定していないことです。

メモリでは timsort を上回り、最悪の場合のパフォーマンスとメモリの両方でクイックソートを上回ります。

しかし、スムーズソートについては聞いたことがありません。誰もそれについて言及したことはなく、ほとんどの議論は他のソート アルゴリズムを中心に展開しているようです。

何故ですか？