デュアルピボットクイックソートとクイックソートの違いは何ですか？

質問

デュアルピボットクイックソートは初めて見ました。 クイックソートのアップグレード版なのでしょうか？

また、デュアルピボットクイックソートとクイックソートの違いは何でしょうか？

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

Javaドキュメントにこんなのがありました。

ソートアルゴリズムはDual-Pivot Quicksortです。 Vladimir Yaroslavskiy, Jon Bentley, and Joshua Blochによるものです。このアルゴリズムは は、他のクイックソートが二次関数的に劣化するような多くのデータセットで O(n log(n))の性能を提供します。 このアルゴリズムは、他のクイックソートの性能が2次関数的に低下するような多くのデータセットにおいて、O(n log(n))の性能を提供し、一般的に 従来の（1ピボット）クイックソートの実装よりも高速です。

そして、Googleの検索結果でこんなのを見つけました。 クイックソートアルゴリズムの理論。

1. 配列からピボットと呼ばれる要素を選びます。
2. 配列の順番を変更し、ピボットより小さい要素はすべてピボットの前に、ピボットより大きい要素はすべてピボットの後に来るようにします。 ピボットより小さい要素はピボットの前に、ピボットより大きい要素はピボットの後に来るように配列を並べ替えます。 どちらかになります)。このように分割した後、ピボット要素は最終的な位置になります。
3. より小さい要素の部分配列とより大きい要素の部分配列を再帰的にソートします。

比較すると、デュアルピボット・クイックソート。

1. 小さな配列 (length < 17) には、挿入ソート アルゴリズムを使用します。
2. 2つのピボット要素P1、P2を選ぶ。例えば、最初の要素 a[left]をP1、最後の要素a[right]をP2として得ることができます。
3. P1はP2より小さくなければならず、そうでなければ入れ替わります。ということで、以下のようなパーツがあります。
   • P1より小さい要素を持つ、left+1 から L-1までのインデックスを持つパートI。
   • P1以上P2以下の要素を持つ、LからK-1までのインデックスを持つパートII。
   • G+1からright-1までのインデックスを持ち、P2より大きい要素を持つパートIII。
   • 部分IVはKからGまでのインデックスを持つ検査される残りの要素を含んでいます。
4. パートIVからの次の要素a[K]は、2つのピボットP1およびP2と比較されます。 と比較され、対応するパートI、II、またはIIIに配置されます。
5. ポインタL、K、Gが対応する方向に変更される。
6. K≦Gの間、手順4～5を繰り返す。
7. ピボット要素P1はパートIの最後の要素と入れ替わります。 ピボット要素P2はパートIIIから最初の要素と入れ替わる。
8. パートI、パートII、パートIIIごとにステップ1〜7が再帰的に繰り返されます。