c++ - 一般的な C++ コンパイラが std::sort と std::stable_sort に使用するアルゴリズムは何ですか?

Question

一般的な C++ コンパイラが std::sort と std::stable_sort に使用するアルゴリズムは何ですか? 標準が特定のパフォーマンス要件しか与えていないことは知っていますが、一般的な実装で実際に使用されているアルゴリズムを知りたいです。

各実装の参照を引用すると、答えはより便利になります。

Answer 1

まず第一に、コンパイラは の実装を提供しませstd::sortん。従来、各コンパイラには標準ライブラリの実装 (コンパイラの組み込みに大きく依存) があらかじめパッケージ化されていますが、理論上は、ある実装を別の実装に交換することができます。非常に良い例の 1 つは、Clang が libstdc++ (従来は gcc にパッケージ化されている) と libc++ (真新しい) の両方をコンパイルすることです。

これが途方に暮れた今...

std::sortは伝統的にintro-sortとして実装されてきました。高レベルの観点からは、比較的標準的なクイック ソートの実装 (O(n ² ) の最悪のケースを回避するための中央値プローブを使用) と小さな入力の挿入ソート ルーチンを組み合わせたものを意味します。ただし、libc++ の実装は若干異なり、TimSort に近いです。入力内の既に並べ替えられたシーケンスを検出し、再度並べ替えを回避するため、完全に並べ替えられた入力で O(n) の動作が発生します。また、小さな入力に対して最適化された並べ替えネットワークも使用します。

std::stable_sort一方、本質的により複雑です。これは、標準の文言そのものから推定できます。十分な追加メモリを割り当てることができる場合 (merge-sort のヒント) 、複雑さは O(n log n) ですが、そうでない場合は O(n log ² n)に退化します。

Answer 2

std::sort例として gcc を取り上げると、それは のイントロソートと のマージソートであることがわかりますstd::stable_sort。

libc ++ コードstd::stable_sortを調べてみると、範囲が十分に大きい場合にマージソートも使用されていることがわかります。

また、注意すべきことの 1 つは、一般的なアプローチは常に上記のいずれかですが、それらはすべてさまざまな特殊なケースに合わせて高度に最適化されているということです。