浅析 std::sort、std::stable_sort 和 std::partial_sort 的实现细节

libu2333 · 2025-08-12 12:13:18 · 算法·理论

本文部分内容来源于网络，侵删。

-1. 前言

众所周知，std::sort 是一个竞赛生常用的 STL 函数，它简洁方便还快速好用，是编码时的不二之选。当然，std::stable_sort 和 std::partial_sort 也是面对特定问题时的不错解决方案。但是，你真的了解这些函数背后的真面目吗？

0. 定位

首先，作为一名 OIer，我们应当知道这三个函数都位于 algorithm 头文件里。但实际上，但你打开这个头文件本身后你会发现，它其实只是一个对外接口式的“空壳子”，实际上是一般由三个内部头文件组成的：bits/stl_algo.h、bits/stl_algobase.h 和 bits/ranges_algo.h（C++17 之后）。

而本文中所讲的三个函数，全部都位于 bits/stl_algo.h 这个头文件里。

1. std::sort

1.1 外部接口

我们不难在 stl_algo.h 里找到 std::sort 函数的原型：

  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      // 一些 concept 检查

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    }

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     _Compare __comp)
    {
      // concept requirements
      // 一些 concept 检查

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

我们可以看到，除了执行一些 GCC 内部的前置检查之外，std::sort 真正的排序功能实际上还是通过调用内部函数 std::__sort 来完成的。

一些问题

1. _GLIBCXX20_CONSTEXPR 是什么？

这实际上是 GCC 所做的一个向下兼容措施。C++20 标准使得 constexpr 函数大大增强，以至于像 std::sort 这样的复杂函数都被标记为可以在编译期计算。然而为了向下兼容较老的标准，GCC 定义了一个 _GLIBCXX20_CONSTEXPR 宏，在 C++20 以下的标准中这个宏什么也不做，但如果编译器使用 C++20 标准编译，这个宏则是 constexpr。

2. __gnu_cxx::__ops::_iter_comp_iter () 是什么？

由于内部函数 std::__sort 实际上比较的是迭代器，然而用户传入的自定义比较函数 / 伪函数一般比较的都是解引用迭代器后得到的值，所以就需要 bits/predefined_ops.h 头文件内的这个函数来把用户传入的函数 / 伪函数包装起来用于迭代器比较。在无自定义比较函数的重载版本里，传给 std::__sort 的 __gnu_cxx::__ops::__iter_less_iter() 比较器也是一样。

1.2 内部版本

我们同样能找到内部函数 std::_sort 的函数原型：

template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
    {
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp);
      std::__final_insertion_sort(__first, __last, __comp);
    }
    }

由此可见，__sort 实际上也是一个“壳子”，真正的排序算法还是依靠于两个内部函数。

我们可以结合这个视频来更深入了解排序的过程：

2:30:14 到 2:30:42 是 std::sort 的全过程。

从视频中我们可以看到，首先算法使用了类似快速排序的方法进行粗略的排序（即 std::__introsort_loop），然后再使用插入排序进行最后的收尾（即 std::__final_insertion_sort）。

实际上，这个排序算法有一个正式的名字：内省排序（Introsort）。

1.3 内省排序

这是整个排序算法的核心。让我们先从函数原型下手：

  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __introsort_loop(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             _Size __depth_limit, _Compare __comp)
    {
      while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          std::__partial_sort(__first, __last, __last, __comp);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);
      __last = __cut;
    }
    }

这个函数接受四个参数。前两个参数很好理解，首尾迭代器，代表一个前闭后开的区间。最后一个参数是比较器，也很好理解。

最重要的部分，也是内省排序相比于快速排序最大的优势，就在于函数的第三个参数：__depth_limit。

简单地说，内省排序使用了一个 限制深度 的操作，如果快速排序的递归深度大于等于最开始传入的 __depth_limit，则放弃快速排序，在小区间内改用稳定的堆排序（std::__partial_sort，具体内容见第三节）。

另外，从代码中我们可以看到，主循环中有一个循环条件：__last - __first > int(_S_threshold)。前两个变量是首尾迭代器，但这个 _S_threshold 是什么？

这其实是内省排序的另一个优化点：众所周知，快排 / 堆排在小区间里的额外开销是很大的，所以当区间大小小于一定长度时（GCC 默认为 16），内省排序会改用插入排序来改善额外开销。这也就是为什么在 std::__sort 函数的最后还要调用 std::__final_insertion_sort。

然后剩下的内容就是快速排序的模板了。

一些问题

1. __depth_limit 一般取多大？

在 std::__sort 实现中，__depth_limit 取的是 std::__lg(__last - __first) * 2，也就是 2 \times \left\lfloor \log_{2} n \right\rfloor。这个取值是约定俗成的，最早可以追溯到发明内省排序的 David Musser 于 1997 年提出该算法的论文中。

2. 为什么要用插入排序来进行收尾，而不是其他 O(n^2) 的排序？

由于快速排序的特性，在长度为 16 及以下的区间中元素已经接近有序，在这时使用插入排序在 O(n^2) 的排序算法中效率最高，甚至可能接近 O(n)。

1.4 快速排序部分

先贴出 std::__unguarded_partition_pivot 函数的源代码。

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline _RandomAccessIterator
    __unguarded_partition_pivot(_RandomAccessIterator __first,
                _RandomAccessIterator __last, _Compare __comp)
    {
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
                  __comp);
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
    }

这就是经典的快排算法的一部分，具体点来说，就是选 基准点 / 枢轴（pivot）。

只要你学过快速排序，那你一定知道：在快速排序中，基准点的选择非常关键，因为基准点的大小直接关系到排序算法的递归深度，从而直接与时间挂钩。因此，GCC 使用了一个折中的办法来选取基准点：三数取中，即代码中的 std::__move_median_to_first 函数。

这个函数的源代码很好理解：

  template<typename _Iterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
               _Iterator __c, _Compare __comp)
    {
      if (__comp(__a, __b))
    {
      if (__comp(__b, __c))
        std::iter_swap(__result, __b);
      else if (__comp(__a, __c))
        std::iter_swap(__result, __c);
      else
        std::iter_swap(__result, __a);
    }
      else if (__comp(__a, __c))
    std::iter_swap(__result, __a);
      else if (__comp(__b, __c))
    std::iter_swap(__result, __c);
      else
    std::iter_swap(__result, __b);
    }

它比较了三个迭代器，然后将中间值放到了 __result 迭代器里。std::iter_swap 的作用就是将两个迭代器的值交换。

std::__unguarded_partition_pivot 中就使用了这个函数，将区间的起始点 __first 设为了基准点，随即调用 std::__unguarded_partition 进行快速排序的核心内容 —— 重排列。

std::__unguarded_partition 的代码如下：

    template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
              _RandomAccessIterator __last,
              _RandomAccessIterator __pivot, _Compare __comp)
    {
      while (true)
    {
      while (__comp(__first, __pivot))
        ++__first;
      --__last;
      while (__comp(__pivot, __last))
        --__last;
      if (!(__first < __last))
        return __first;
      std::iter_swap(__first, __last);
      ++__first;
    }
    }

相信学过快速排序的 OIer 看到这个函数就会会心一笑：这不就是快速排序的重排列吗？的确，这个函数就是用双指针的方法重新排列给定的前闭后开区间，使其符合快速排序的要求。至此，内省排序的第一轮流程 —— 粗略排序彻底完成。

一些问题

1. 为什么有些函数的前面会有 `__unguarded`？

不知道各位有没有注意到，所有的带 __unguarded 的函数都没有判定迭代器是否越界。这是因为为了提高效率，GCC 认定在执行这些函数时 不会产生未定义行为，因此就无需进行越界判断。但是这样做会导致这个函数没有越界保护，也就是 unguarded 的来由。

2. 为什么要使用 `std::iter_swap` 交换迭代器，而不是直接用 `std::swap`？

这是一个新手常犯的错误。

迭代器本质上类似指针，交换迭代器本身毫无意义，无法改变数组内值的顺序，甚至可能产生未定义行为。正确的做法应该是交换迭代器解引用后得到的值。

1.5 最后的收尾（插入排序）

最后一步，自然是使用 std::__final_insertion_sort 来进行小区间的插入排序。仍然是先看代码：

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __final_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last, _Compare __comp)
    {
      if (__last - __first > int(_S_threshold))
    {
      std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
                      __comp);
    }
      else
    std::__insertion_sort(__first, __last, __comp);
    }

看上去这一大堆很唬人，实际上这个函数仍然只是一个经过整合的对外接口。实际上它只做一件事：

区间长度超过阈值（GCC 定义为 16），先用普通插入排序（std::__insertion_sort）对前面阈值个元素排序，再用无边界检查的版本（std::__unguarded_insertion_sort）排序剩余部分。
区间长度不超过阈值，直接用普通插入排序。

至于插入排序具体如何实现，还是要看下面的代码：

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __unguarded_linear_insert(_RandomAccessIterator __last,
                  _Compare __comp)
    {
      typename iterator_traits<_RandomAccessIterator>::value_type
    __val = _GLIBCXX_MOVE(*__last);
      _RandomAccessIterator __next = __last;
      --__next;
      while (__comp(__val, __next))
    {
      *__last = _GLIBCXX_MOVE(*__next);
      __last = __next;
      --__next;
    }
      *__last = _GLIBCXX_MOVE(__val);
    }

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __insertion_sort(_RandomAccessIterator __first,
             _RandomAccessIterator __last, _Compare __comp)
    {
      if (__first == __last) return;

      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    {
      if (__comp(__i, __first))
        {
          typename iterator_traits<_RandomAccessIterator>::value_type
        __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);
        }
      else
        std::__unguarded_linear_insert(__i,
                __gnu_cxx::__ops::__val_comp_iter(__comp));
    }
    }

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __unguarded_insertion_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __last, _Compare __comp)
    {
      for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
    std::__unguarded_linear_insert(__i,
                __gnu_cxx::__ops::__val_comp_iter(__comp));
    }

这一串代码实现了三个函数：普通插入排序（std::__insertion_sort）、无边界检查的插入排序（std::__unguarded_insertion_sort）和插入排序的帮手函数 std::__unguarded_linear_insert。

std::__unguarded_linear_insert 的功能是将位于给定的 __last 迭代器内的元素按升序插入其前面已经有序的区间中。

对于 std::__insertion_sort，主体是从第二个元素开始遍历：如果当前元素比第一个元素小，说明它是最小值，要把它移到最前面。通过 _GLIBCXX_MOVE_BACKWARD3 把区间 [__first, __i) 后移一个位置，为插入腾出空间。否则，调用帮手函数 __unguarded_linear_insert 插入当前位置。这保证了最前面有个哨兵元素（最小元素），后续插入可以不用边界检查。

对于 std::__unguarded_insertion_sort，它直接调用 __unguarded_linear_insert，无须边界判断，比 std::__insertion_sort 性能更好。

至此，std::sort 的内容就已经分析完毕，算法的流程大致如下：

调用 std::__introsort_loop 进行快速排序，如果递归深度大于设定的值则使用堆排序。
快排完成后，调用 std::__final_insertion_sort 进行插入排序。

发明内省排序的 Devid Musser 经过研究指出，在为三数取中法快速排序精心设计的 n = 10^5 的序列上，内省排序的运行时间是快速排序的 \frac{1}{200}，效果极佳。

一些问题

1. 为什么要使用两个版本的插入排序？

普通插入排序（std::__insertion_sort）需要在插入过程中判断边界，防止越界，适合处理区间的最前面几个元素。

无边界插入排序（std::__unguarded_insertion_sort）假设前面已经有序的哨兵区间，插入剩余元素时就可以省去边界检查，性能更优。

2. _GLIBCXX_MOVE 是什么？

它是 GCC 标准库内部用来实现 移动语义 的宏，功能相当于 std::move。

目的是将左值转换为右值引用，从而启用移动构造和移动赋值，避免不必要的复制，提高效率。

2. std::stable_sort

2.1 外部接口

std::stable_sort 使用优化后的归并排序实现。

我们可以从 bits/stl_algo.h 头文件中找到 std::stable_sort 函数的原型：

  template<typename _RandomAccessIterator>
    inline void
    stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      // 一些 concept 检查

      _GLIBCXX_STD_A::__stable_sort(__first, __last,
                    __gnu_cxx::__ops::__iter_less_iter());
    }
  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _Compare __comp)
    {
      // concept requirements
      // 一些 concept 检查

      _GLIBCXX_STD_A::__stable_sort(__first, __last,
                    __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

它的结构与 std::sort 差不多，在此不再赘述。值得注意的是，__sort 在 std 命名空间里，然而 __stable_sort 却在另一个内部命名空间 _GLIBCXX_STD_A 里，原因不详。

2.2 内部版本

先看代码。

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _DistanceType;

      if (__first == __last)
    return;

#if _GLIBCXX_HOSTED
      typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
      // __stable_sort_adaptive sorts the range in two halves,
      // so the buffer only needs to fit half the range at once.
      _TmpBuf __buf(__first, (__last - __first + 1) / 2);

      if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
    std::__stable_sort_adaptive(__first,
                    __first + _DistanceType(__buf.size()),
                    __last, __buf.begin(), __comp);
      else if (__builtin_expect(__buf.begin() == 0, false))
    std::__inplace_stable_sort(__first, __last, __comp);
      else
    std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
                       _DistanceType(__buf.size()), __comp);
#else
      std::__inplace_stable_sort(__first, __last, __comp);
#endif
    }

首先，函数申请了一块连续的内存空间 __buf，存储元素的副本。

如果成功分配了需要的内存，函数调用 std::__stable_sort_adaptive，它利用这块缓冲区进行更高效的分块归并排序。

如果分配缓冲区失败，这时函数退化成 std::__inplace_stable_sort，一种原地归并排序，不依赖额外内存，但性能略差。

如果缓冲区大小不足，调用 std::__stable_sort_adaptive_resize，会尝试调整策略，折中使用可用缓冲区。

如果不处于托管环境，直接原地排序。

让我们先看 std::__stable_sort_adaptive 的代码：

  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
    void
    __stable_sort_adaptive(_RandomAccessIterator __first,
               _RandomAccessIterator __middle,
               _RandomAccessIterator __last,
               _Pointer __buffer, _Compare __comp)
    {
      std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
      std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);

      std::__merge_adaptive(__first, __middle, __last,
                __middle - __first, __last - __middle,
                __buffer, __comp);
    }

它调用了 std::__merge_sort_with_buffer 来进行归并排序，再使用 std::__merge_adaptive 函数来实现归并排序中的合并操作。

std::__inplace_stable_sort 也是同理：

  template<typename _RandomAccessIterator, typename _Compare>
    void
    __inplace_stable_sort(_RandomAccessIterator __first,
              _RandomAccessIterator __last, _Compare __comp)
    {
      if (__last - __first < 15)
    {
      std::__insertion_sort(__first, __last, __comp);
      return;
    }
      _RandomAccessIterator __middle = __first + (__last - __first) / 2;
      std::__inplace_stable_sort(__first, __middle, __comp);
      std::__inplace_stable_sort(__middle, __last, __comp);
      std::__merge_without_buffer(__first, __middle, __last,
                  __middle - __first,
                  __last - __middle,
                  __comp);
    }

当区间长度小于等于 15（即小于 GCC 的小区间阈值 _S_threshold）时，函数直接调用之前讲过的 std::__insertion_sort 函数进行插入排序，以避免递归深度过大。

否则，函数递归调用自身，再调用 std::__merge_without_buffer 函数实现没有缓冲区的合并操作。

一些问题

1. 托管环境和 _GLIBCXX_HOSTED 是什么？

托管环境指的是程序运行在操作系统之上，能够使用完整的标准库和系统服务的环境。在这种环境下，程序通常包含一个 main 函数，操作系统负责程序的启动、内存管理、输入输出等功能。GCC 默认假设目标环境是托管环境，因此会启用标准库的完整功能，并进行相应的优化。

_GLIBCXX_HOSTED 是一个编译器定义的宏，用于确认是否处于托管环境。

2. __builtin_expect 又是什么？

__builtin_expect 是 GCC 提供的一个内建函数，用于向编译器提供分支预测信息，以优化条件分支的性能。它的作用是告诉编译器某个条件表达式的结果更可能是某个特定值，从而帮助编译器生成更高效的汇编代码。

2.3 带缓冲区的归并排序

让我们先看 std::__merge_sort_with_buffer 的代码。

  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
    void
    __merge_sort_with_buffer(_RandomAccessIterator __first,
                 _RandomAccessIterator __last,
                 _Pointer __buffer, _Compare __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _Distance;

      const _Distance __len = __last - __first;
      const _Pointer __buffer_last = __buffer + __len;

      _Distance __step_size = _S_chunk_size;
      std::__chunk_insertion_sort(__first, __last, __step_size, __comp);

      while (__step_size < __len)
    {
      std::__merge_sort_loop(__first, __last, __buffer,
                 __step_size, __comp);
      __step_size *= 2;
      std::__merge_sort_loop(__buffer, __buffer_last, __first,
                 __step_size, __comp);
      __step_size *= 2;
    }
    }

首先，函数调用 std::__chunk_insertion_sort 把整个数组分成小块，用插入排序对每块排序。

接下来的部分就是非常典型的自底向上归并排序：

函数先调用 std::__merge_sort_loop 对连续的两段长度为步长 __step_size 的区间进行归并，并把结果写入缓冲区。
接下来，步长翻倍，然后调用同样的函数将结果写入原区间，步长再次翻倍。

让我们结合代码来更深入的理解：

  template<typename _InputIterator, typename _OutputIterator,
       typename _Compare>
    _OutputIterator
    __move_merge(_InputIterator __first1, _InputIterator __last1,
         _InputIterator __first2, _InputIterator __last2,
         _OutputIterator __result, _Compare __comp)
    {
      while (__first1 != __last1 && __first2 != __last2)
    {
      if (__comp(__first2, __first1))
        {
          *__result = _GLIBCXX_MOVE(*__first2);
          ++__first2;
        }
      else
        {
          *__result = _GLIBCXX_MOVE(*__first1);
          ++__first1;
        }
      ++__result;
    }
      return _GLIBCXX_MOVE3(__first2, __last2,
                _GLIBCXX_MOVE3(__first1, __last1,
                       __result));
    }

  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
       typename _Distance, typename _Compare>
    void
    __merge_sort_loop(_RandomAccessIterator1 __first,
              _RandomAccessIterator1 __last,
              _RandomAccessIterator2 __result, _Distance __step_size,
              _Compare __comp)
    {
      const _Distance __two_step = 2 * __step_size;

      while (__last - __first >= __two_step)
    {
      __result = std::__move_merge(__first, __first + __step_size,
                       __first + __step_size,
                       __first + __two_step,
                       __result, __comp);
      __first += __two_step;
    }
      __step_size = std::min(_Distance(__last - __first), __step_size);

      std::__move_merge(__first, __first + __step_size,
            __first + __step_size, __last, __result, __comp);
    }

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __chunk_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last,
               _Distance __chunk_size, _Compare __comp)
    {
      while (__last - __first >= __chunk_size)
    {
      std::__insertion_sort(__first, __first + __chunk_size, __comp);
      __first += __chunk_size;
    }
      std::__insertion_sort(__first, __last, __comp);
    }

其中，std::__chunk_insertion_sort 把整个区间分成若干长度为 __chunk_size 的小块，然后对每块调用 std::__insertion_sort 进行插入排序。

std::__merge_sort_loop 则每次取两个连续的块 [__first, __first+__step_size) 和 [__first+__step_size, __first+2*__step_size)，然后调用 std::__move_merge 合并，结果写入 __result。最后移动 __first 到下两个块的起始位置，重复循环。剩余长度不足两个步长的区间单独处理。

std::__move_merge 的作用则是使用移动语义（_GLIBCXX_MOVE）合并两个有序区间。

接下来是归并部分：

  template<typename _InputIterator1, typename _InputIterator2,
       typename _OutputIterator, typename _Compare>
    void
    __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
              _InputIterator2 __first2, _InputIterator2 __last2,
              _OutputIterator __result, _Compare __comp)
    {
      while (__first1 != __last1 && __first2 != __last2)
    {
      if (__comp(__first2, __first1))
        {
          *__result = _GLIBCXX_MOVE(*__first2);
          ++__first2;
        }
      else
        {
          *__result = _GLIBCXX_MOVE(*__first1);
          ++__first1;
        }
      ++__result;
    }
      if (__first1 != __last1)
    _GLIBCXX_MOVE3(__first1, __last1, __result);
    }

  /// This is a helper function for the __merge_adaptive routines.
  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
       typename _BidirectionalIterator3, typename _Compare>
    void
    __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
                   _BidirectionalIterator1 __last1,
                   _BidirectionalIterator2 __first2,
                   _BidirectionalIterator2 __last2,
                   _BidirectionalIterator3 __result,
                   _Compare __comp)
    {
      if (__first1 == __last1)
    {
      _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
      return;
    }
      else if (__first2 == __last2)
    return;

      --__last1;
      --__last2;
      while (true)
    {
      if (__comp(__last2, __last1))
        {
          *--__result = _GLIBCXX_MOVE(*__last1);
          if (__first1 == __last1)
        {
          _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
          return;
        }
          --__last1;
        }
      else
        {
          *--__result = _GLIBCXX_MOVE(*__last2);
          if (__first2 == __last2)
        return;
          --__last2;
        }
    }
    }

std::__merge_adaptive 函数首先计算左半部分和右半部分的长度，如果其中一部分为空，则直接返回。如果两部分的长度都小于等于阈值 _S_threshold，则使用插入排序对整个区间进行排序。如果只有一部分的长度小于等于阈值，则对该部分使用插入排序，另一部分使用归并排序。如果两部分的长度都大于阈值，则直接使用归并排序。

在合并阶段，该函数并不是简单地调用同样逻辑的子函数，而是根据左右子区间的长度选择前向或后向合并策略，以提高性能。这两种策略对应的函数就是 std::__move_merge_adaptive 与 std::__move_merge_adaptive_backward。

std::__move_merge_adaptive 从两段有序区间中反复选取较小值移动到目标区间，并用 _GLIBCXX_MOVE 优化性能，最后直接移动剩余的元素。

std::_move_merge_adaptive_backward 则正好相反，先将末尾元素向 __result 的末尾写入，保证不会覆盖未处理数据。当某一段耗尽，其剩余部分反向移动至目标区。

2.4 缓冲区大小不足时的归并操作

让我们先看看 std::__merge_adaptive_resize 函数的代码。

  template<typename _BidirectionalIterator, typename _Distance,
       typename _Pointer, typename _Compare>
    void
    __merge_adaptive_resize(_BidirectionalIterator __first,
                _BidirectionalIterator __middle,
                _BidirectionalIterator __last,
                _Distance __len1, _Distance __len2,
                _Pointer __buffer, _Distance __buffer_size,
                _Compare __comp)
    {
      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
    std::__merge_adaptive(__first, __middle, __last,
                  __len1, __len2, __buffer, __comp);
      else
    {
      _BidirectionalIterator __first_cut = __first;
      _BidirectionalIterator __second_cut = __middle;
      _Distance __len11 = 0;
      _Distance __len22 = 0;
      if (__len1 > __len2)
        {
          __len11 = __len1 / 2;
          std::advance(__first_cut, __len11);
          __second_cut
        = std::__lower_bound(__middle, __last, *__first_cut,
                     __gnu_cxx::__ops::__iter_comp_val(__comp));
          __len22 = std::distance(__middle, __second_cut);
        }
      else
        {
          __len22 = __len2 / 2;
          std::advance(__second_cut, __len22);
          __first_cut
        = std::__upper_bound(__first, __middle, *__second_cut,
                     __gnu_cxx::__ops::__val_comp_iter(__comp));
          __len11 = std::distance(__first, __first_cut);
        }

      _BidirectionalIterator __new_middle
        = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
                     _Distance(__len1 - __len11), __len22,
                     __buffer, __buffer_size);
      std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
                       __len11, __len22,
                       __buffer, __buffer_size, __comp);
      std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
                       _Distance(__len1 - __len11),
                       _Distance(__len2 - __len22),
                       __buffer, __buffer_size, __comp);
    }
    }

std::__merge_adaptive_resize 函数的主要作用是在归并排序过程中，当临时缓冲区的大小不足以一次性容纳需要归并的数据时，动态地调整归并策略，使排序仍然能高效完成。

该函数首先会检查当前分配的缓冲区能否容纳其中一个子区间的全部元素。如果能，就采用一次性拷贝较小的子区间到缓冲区的方法，这样归并时只需要从缓冲区和另一半直接比较并写回即可。如果缓冲区仍然太小，函数就会递归地将归并任务拆分成更小的区间，直到每一部分都能用现有缓冲区完成归并。在拆分时，它会优先划分成左右平衡的区间，减少递归深度。

在调整归并策略的过程中，有一个函数至关重要。先放代码。

  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
       typename _Distance>
    _BidirectionalIterator1
    __rotate_adaptive(_BidirectionalIterator1 __first,
              _BidirectionalIterator1 __middle,
              _BidirectionalIterator1 __last,
              _Distance __len1, _Distance __len2,
              _BidirectionalIterator2 __buffer,
              _Distance __buffer_size)
    {
      _BidirectionalIterator2 __buffer_end;
      if (__len1 > __len2 && __len2 <= __buffer_size)
    {
      if (__len2)
        {
          __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
          _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
          return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
        }
      else
        return __first;
    }
      else if (__len1 <= __buffer_size)
    {
      if (__len1)
        {
          __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
          _GLIBCXX_MOVE3(__middle, __last, __first);
          return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
        }
      else
        return __last;
    }
      else
    return std::rotate(__first, __middle, __last);
    }

std::__rotate_adaptive 函数在归并排序的分治过程中，高效地调整两个相邻区间的位置，以便后续能够分别归并。

它会优先利用缓冲区来减少元素移动次数：如果后半段长度较短且能放进缓冲区，就先将它拷贝到缓冲区，再将前半段整体后移，最后把缓冲区的元素移到前面；反之，如果前半段较短且能放进缓冲区，就先把它拷贝到缓冲区，再将后半段整体前移，最后把缓冲区内容放到末尾。如果两段都比缓冲区大，就退回到标准库的 std::rotate 进行原地旋转。

这样，我们就能在缓冲区足够时减少数据搬移的成本，在缓冲区不足时保证功能正确。

2.5 原地排序时的归并操作

当缓冲区分配失败或者系统不处于托管环境时，原地归并排序 std::__inplace_stable_sort 就只能调用无缓冲区的合并函数，std::__merge_without_buffer。

它的源代码如下：

  template<typename _BidirectionalIterator, typename _Distance,
       typename _Compare>
    void
    __merge_without_buffer(_BidirectionalIterator __first,
               _BidirectionalIterator __middle,
               _BidirectionalIterator __last,
               _Distance __len1, _Distance __len2,
               _Compare __comp)
    {
      if (__len1 == 0 || __len2 == 0)
    return;

      if (__len1 + __len2 == 2)
    {
      if (__comp(__middle, __first))
        std::iter_swap(__first, __middle);
      return;
    }

      _BidirectionalIterator __first_cut = __first;
      _BidirectionalIterator __second_cut = __middle;
      _Distance __len11 = 0;
      _Distance __len22 = 0;
      if (__len1 > __len2)
    {
      __len11 = __len1 / 2;
      std::advance(__first_cut, __len11);
      __second_cut
        = std::__lower_bound(__middle, __last, *__first_cut,
                 __gnu_cxx::__ops::__iter_comp_val(__comp));
      __len22 = std::distance(__middle, __second_cut);
    }
      else
    {
      __len22 = __len2 / 2;
      std::advance(__second_cut, __len22);
      __first_cut
        = std::__upper_bound(__first, __middle, *__second_cut,
                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      __len11 = std::distance(__first, __first_cut);
    }

      _BidirectionalIterator __new_middle
    = std::rotate(__first_cut, __middle, __second_cut);
      std::__merge_without_buffer(__first, __first_cut, __new_middle,
                  __len11, __len22, __comp);
      std::__merge_without_buffer(__new_middle, __second_cut, __last,
                  __len1 - __len11, __len2 - __len22, __comp);
    }

这个函数首先处理掉最简单的两种情况：如果任一子区间为空就直接返回；如果总长度为 2，则只需比较两个元素并决定是否交换即可。

随后进入递归分治逻辑：它始终选择较长的一段取中点（避免极端不平衡的递归），然后在另一段中使用 std::lower_bound（或对称使用 std::upper_bound）寻找对应的切分位置，这样可以确保 __first_cut 左边的元素均小于等于 __second_cut 左边的元素，从而保证归并正确与稳定性。接下来使用 std::rotate 把 [__first_cut, __middle) 和 [__middle, __second_cut) 两个区间的位置交换过来，使得待归并的两个小问题都变成相邻的两段。然后分别递归调用自身，归并两组子区间。

虽然没有缓冲区的归并操作在代码实现上相对简单，但是它也有一个致命的缺陷：时间常数很大。所以，在一般情况下，GCC 都会选择以空间换时间，使用带缓冲区的归并排序。

3. std::partial_sort

相比于 std::sort 和 std::stable_sort，std::partial_sort（及其变体 std::partial_sort_copy）鲜有人提起，因为其并非传统意义上的“排序”，而是解决一类特定问题：数组中的前 k 个数。

具体来说，std::partial_sort 使用 堆排序，将数组按 __comp() 排序后的前 __middle - __first 个数移动到数组开头，其余元素不保证有特定顺序。其变体 std::partial_sort_copy 的作用则是将数组按 __comp() 排序后的前 __result_last - __result_first 个元素按排序后顺序复制到 __result_first 迭代器所在的容器中。

由于这两个函数的代码实现大同小异，接下来，我们将聚焦于 std::partial_sort 函数，剖析它的内部实现。

3.1 外部接口

std::partial_sort 的函数原型与 std::sort 和 std::stable_sort 基本相同，在此不过多展开。

3.2 内部版本

与前面讲解的两个函数一样，std::partial_sort 对应的内部函数也是带双下划线的版本（实际上是编译器内部实现），std::__partial_sort。下面是它的源代码。

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __partial_sort(_RandomAccessIterator __first,
           _RandomAccessIterator __middle,
           _RandomAccessIterator __last,
           _Compare __comp)
    {
      std::__heap_select(__first, __middle, __last, __comp);
      std::__sort_heap(__first, __middle, __comp);
    }

从这里，我们就能从调用的两个内部函数名看出，std::partial_sort 实际上使用的是 堆排序！

接下来，我们就要脱离 partial_sort 的范围，开始解读 GCC 内部堆的实现。

3.2 维护一个二叉堆

在离开 std::partial_sort 所在的 bits/stl_algo.h 之前，我们先来看看最后一个位于该头文件的函数的源代码：

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __heap_select(_RandomAccessIterator __first,
          _RandomAccessIterator __middle,
          _RandomAccessIterator __last, _Compare __comp)
    {
      std::__make_heap(__first, __middle, __comp);
      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
    if (__comp(__i, __first))
      std::__pop_heap(__first, __middle, __i, __comp);
    }

由此可见，这个函数也只是将一些堆操作函数集成在一起而已。

那么接下来，按理来说我们就需要在这个函数的前面找到堆操作对应的函数。然而，我们发现：在 bits/stl_algo.h 头文件里，我们并没有发现它们的身影。它们在哪里呢？

我们注意到，在文件的开头，GCC 包含了一个名为 bits/stl_heap.h 的头文件。这应该就是我们要找的东西！

怀着激动的心情，我们终于找到了这些堆函数的庐山真面目！下面是 std::__push_heap、std::__adjust_heap 和 std::__make_heap 函数的代码。

  template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
       typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __push_heap(_RandomAccessIterator __first,
        _Distance __holeIndex, _Distance __topIndex, _Tp __value,
        _Compare& __comp)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
    {
      *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
      __holeIndex = __parent;
      __parent = (__holeIndex - 1) / 2;
    }
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
    }

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
          _Distance __len, _Tp __value, _Compare __comp)
    {
      const _Distance __topIndex = __holeIndex;
      _Distance __secondChild = __holeIndex;
      while (__secondChild < (__len - 1) / 2)
    {
      __secondChild = 2 * (__secondChild + 1);
      if (__comp(__first + __secondChild,
             __first + (__secondChild - 1)))
        __secondChild--;
      *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
      __holeIndex = __secondChild;
    }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
    {
      __secondChild = 2 * (__secondChild + 1);
      *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             + (__secondChild - 1)));
      __holeIndex = __secondChild - 1;
    }
      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
    __cmp(_GLIBCXX_MOVE(__comp));
      std::__push_heap(__first, __holeIndex, __topIndex,
               _GLIBCXX_MOVE(__value), __cmp);
    }

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _Compare& __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
      _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
      _DistanceType;

      if (__last - __first < 2)
    return;

      const _DistanceType __len = __last - __first;
      _DistanceType __parent = (__len - 2) / 2;
      while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
    }

这三个函数加起来，就足够维护一个二叉堆了。让我们一个个分析这些函数：

3.2.1 插入（`std::__push_heap`）

该函数向已经是一个堆的数组末尾“插入” 一个新元素，然后对该元素进行上浮操作，使它重新满足堆性质。

过程：把新元素当成一个“洞（hole）” 放在末尾，和它的父节点比较，如果比父节点更大（最大堆）就把父节点向下移，洞上移，直到不再比父节点大或者到达根节点。

3.2.2 调整（`std::__adjust_heap`）

在某个位置删除（或替换）元素后进行下沉和上浮操作，使数组重新成为一个堆。

过程：假设位置 __holeIndex 上的“洞” 之前存有被删除 / 挪走的元素，把较大的孩子节点向上填洞（下滤），一直下走到底部，然后再向上使用 __push_heap 把新元素插入到正确的位置。

3.2.3 建堆（`std::__make_heap`）

该函数用的是经典的“从第一个非叶子结点开始不断下滤” 法。

首先，我们找到最后一个非叶子节点 (__len-2)/2。从它开始，向前依次对每个节点做一次下滤（std::__adjust_heap）操作，把该节点调整到它在堆中的正确位置上。

容易证明，经过这个过程后，整棵树就满足堆序性。

3.3 下一步：只排序前 k 个元素

经过建堆操作之后，std::__heap_select 会遍历 [__middle, __last) 范围内的每个迭代器，将这些元素弹出堆。

弹出操作的代码十分简单：

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Compare& __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _DistanceType;

      _ValueType __value = _GLIBCXX_MOVE(*__result);
      *__result = _GLIBCXX_MOVE(*__first);
      std::__adjust_heap(__first, _DistanceType(0),
             _DistanceType(__last - __first),
             _GLIBCXX_MOVE(__value), __comp);
    }

它只将传入的迭代器移到数组（堆）末尾，然后调用 std::__adjust_heap 保证堆序性。这也是使用 std::partial_sort 排序后数组其余元素不保证有特定顺序的原因。

最后的最后，std::__partial_sort 调用了 std::__sort_heap 函数来收尾：

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _Compare& __comp)
    {
      while (__last - __first > 1)
    {
      --__last;
      std::__pop_heap(__first, __last, __last, __comp);
    }
    }

这个函数只干了一件事：销毁堆。

在把堆销毁完成之后，原数组就变成了一个前 k 个元素有序，剩余元素乱序的数组。

我们可以看出：std::partial_sort 实际上是将原数组 整体排了一遍序 之后再弹出剩余元素，以此来保证前 k 个元素有序。这实际上时间常数很大，也是 std::partial_sort 不常用的原因之一。

INF. 结语

在这篇文章中，我们分析了 std::sort、std::stable_sort 和 std::partial_sort 的实现细节，具体剖析了内部的实现方法，以及算法执行的过程。

需要注意的是，本篇文章提供的代码全部是 GCC 13.2.0 的内部实现，不保证 所有提到的双下划线开头的内部函数都能在工程或竞赛中使用。实际上，就算是编译器版本相同也不推荐在工程中使用任何以双下划线开头的内部函数，以增强代码可移植性。

本篇文章部分内容由 ChatGPT 5 润色。

浅析 std::sort、std::stable_sort 和 std::partial_sort 的实现细节

-1. 前言

0. 定位

1. std::sort

1.1 外部接口

一些问题

1. _GLIBCXX20_CONSTEXPR 是什么？

2. __gnu_cxx::__ops::_iter_comp_iter () 是什么？

1.2 内部版本

1.3 内省排序

一些问题

1. __depth_limit 一般取多大？

2. 为什么要用插入排序来进行收尾，而不是其他 O(n^2) 的排序？

1.4 快速排序部分

一些问题

1. 为什么有些函数的前面会有 __unguarded？

2. 为什么要使用 std::iter_swap 交换迭代器，而不是直接用 std::swap？

1.5 最后的收尾（插入排序）

一些问题

1. 为什么要使用两个版本的插入排序？

2. _GLIBCXX_MOVE 是什么？

2. std::stable_sort

2.1 外部接口

2.2 内部版本

一些问题

1. 托管环境和 _GLIBCXX_HOSTED 是什么？

2. __builtin_expect 又是什么？

2.3 带缓冲区的归并排序

2.4 缓冲区大小不足时的归并操作

2.5 原地排序时的归并操作

3. std::partial_sort

3.1 外部接口

3.2 内部版本

3.2 维护一个二叉堆

3.2.1 插入（std::__push_heap）

3.2.2 调整（std::__adjust_heap）

3.2.3 建堆（std::__make_heap）

3.3 下一步：只排序前 k 个元素

INF. 结语

1. 为什么有些函数的前面会有 `__unguarded`？

2. 为什么要使用 `std::iter_swap` 交换迭代器，而不是直接用 `std::swap`？

3.2.1 插入（`std::__push_heap`）

3.2.2 调整（`std::__adjust_heap`）

3.2.3 建堆（`std::__make_heap`）