排序是实际生产和算法竞赛中都经常会用到的东西，也是理论计算机研究相对比较多的领域。基于比较的排序的理论下界非常容易获得，然而还是没有算法能够确切地达到这个下界，目前最好的逼近是 Merge-Insertion ，可以在规模比较小的时候严格取到下界。https://en.wikipedia.org/wiki/Merge-insertion_sort
    C++ 以速度快著称，那么标准库里实现的排序使用的是什么算法呢？
    根据 cppref ，我们找到 libstdc++ 的实现代码：

    1. template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    2.     void
    3.     __introsort_loop(_RandomAccessIterator __first,
    4.              _RandomAccessIterator __last,
    5.              _Size __depth_limit, _Compare __comp)
    6.     {
    7.       while (__last - __first > int(_S_threshold))
    8.     {
    9.       if (__depth_limit == 0)
    10.         {
    11.           std::__partial_sort(__first, __last, __last, __comp);
    12.           return;
    13.         }
    14.       --__depth_limit;
    15.       _RandomAccessIterator __cut =
    16.         std::__unguarded_partition_pivot(__first, __last, __comp);
    17.       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
    18.       __last = __cut;
    19.     }
    20.     }
    22.   // sort
    24.   template<typename _RandomAccessIterator, typename _Compare>
    25.     inline void
    26.     __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
    27.        _Compare __comp)
    28.     {
    29.       if (__first != __last)
    30.     {
    31.       std::__introsort_loop(__first, __last,
    32.                 std::__lg(__last - __first) * 2,
    33.                 __comp);
    34.       std::__final_insertion_sort(__first, __last, __comp);
    35.     }
    36.     }

    这里截取了一个片段，我们可以看到它的算法实际上是 intro sort 算法。这是一种融合算法，在数据规模大于 3 的时候我们使用快排，同时记录一个深度的余额（一开始的时候设为C 中的 std::sort - 图1）。每次递归的时候深度的余额就会自减，如果余额不足就会转而使用堆排，防止遇到非常极端的数据快排会被卡到C 中的 std::sort - 图2。如果递归到了数据规模小于等于 3 的时候就会使用插入排序。