首先：编译器不提供的 任何
实现std::sort。传统上，每个编译器都预先打包了一个标准库实现（这在很大程度上依赖于编译器的内置程序），但从理论上讲，您可以将一种实现换成另一种。一个很好的例子是Clang编译了libstdc
（传统上与gcc打包）和libc （全新）。

现在，这已不复存在…

std::sort传统上已作为 intro-sort实现
。从高级的角度来看，这意味着相对标准的快速排序实现（通过一些中位数探测来避免O（n 2）最坏的情况），以及针对小输入的插入排序例程。但是，libc
++实现略有不同，并且更接近TimSort：它检测输入中已经排序的序列，并避免再次对其进行排序，从而导致对完全排序的输入进行O（n）行为。它还将优化的分类网络用于少量输入。

std::stable_sort另一方面，从本质上讲更为复杂。可以从标准的措辞推断出： 如果 可以分配足够的额外内存（在 merge-sort
处提示）， 则 复杂度为O（n log n），但 如果 不能分配则退化为O（n log 2 n）。