`std :: sort`在内部使用什么魔法使它更快？

Question

我有一个简单的quicksort实现,顺便说一下:

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end)
{
  if (begin != end)
  {
    const auto pivot = *(begin + distance(begin, end) / 2);
    const IteratorType sep = std::partition(begin, end, [pivot](typename IteratorType::value_type v){ return (v < pivot); });

    if (sep != begin)
    {
      quicksort(begin, sep);
    }

    if (sep != end)
    {
      quicksort(sep + 1, end);
    }
  }
}

在1000000个元素数组上测试它需要永远(6300毫秒),然后有时会死于递归,而std::sort需要30毫秒.

当然,我不希望我的糟糕实现速度如此之快,std::sort但又怎么会有这么大的差异呢？

我理解std::sort使用比简单的快速排序更复杂的东西(我相信它是内向的)可以防止递归级别和东西太过分.但是,是否有一些明显我遗漏的东西可以解释如此巨大的差异？

改变箭头的大小表明差异因素不是恒定的,实际上它似乎增长了n².

Answer 1

首先检查更好的主元选择（通常使用中位数 3）并消除递归的一个分支以节省堆栈空间。

枢轴选择对整体算法性能影响最大，因为它决定了 N*log(n) 和 N^2 之间的差异。