Goは次のリリースからpdqsortを採用予定

"Pattern-defeating QuickSort"

• ランダムクイックソートの高速な平均ケースとヒープソートの高速な最悪ケースを組み合わせ、特定のパターンの入力に対しては線形時間を達成する最新のソートアルゴリズム
  → Intro Sort（基本的にはクイックソートだが、再帰が深くなるとヒープソートを使う）を改良した拡張
• 現在、C++ および Rust の実装はすでに存在する

[xguru]

関連記事

• この記事の HN リンク Go will use pdqsort in next release
• Changing std::sort at Google’s Scale and Beyond