大家好，我是阿秀。
如果你有过很多场互联网校招或者社招面试经验的话，你一定遇到过一个经典面试问题：“sort算法的底层是什么？”。
关于这个用提，大多数人的回答都是千篇一律的快速排序，少数人则会回答sort的底层是快排和堆排，但其实远不止如此。
这里拿C++中的std::sort算法举例，从源码角度剖析一下sort算法（其余语言的剖析思路也基本一致，感兴趣的可以试着自己探究一下）。
回答重点
std::sort 非常高效，它不单纯是快速排序，而是使用了一种名为 introspective sort（内省排序）的算法。
内省排序是快速排序、堆排序和插入排序的结合体，它结合这些算法优点的同时避免它们的缺点，特别是快速排序在最坏情况下的性能下降问题。
注意：本题介绍，仅限于GCC的源码实现。
扩展知识
快速排序：内省排序首先使用快速排序算法。利用快速排序分而治之的特点，通过选取一个pivot元素，将数组分为两个子数组，一个包含小于pivot的元素，另一个包含大于pivot的元素，然后递归地对这两个子数组进行快速排序。快速排序在平均情况下非常高效，时间复杂度为 O(n log n)。
/// This is a helper function for the sort routine.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;}}// sorttemplate <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);}}
内省排序：通过限制快速排序递归深度，避免其最坏情况的性能问题。递归深度的限制基于输入数组的大小，通常是对数组长度取对数然后乘以一个常数（在 GCC 实现中是 2 * log(len)）。如果排序过程中递归深度超过了这个限制，算法会切换到堆排序。
/// This is a helper function for the sort routine.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;}}// sorttemplate <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);}}
堆排序：当快速排序的递归深度超过限制时，内省排序会切换到堆排序，保证最坏情况下的时间复杂度为 O(n log n)。堆排序不依赖于数据的初始排列，因此它的性能无论在最好、平均和最坏情况下都是稳定的。
/// This is a helper function for the sort routine.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;}}
插入排序：最后，当数组的大小减小到一定程度时，内省排序会使用插入排序来处理小数组。插入排序在小数组上非常高效，尽管它的平均和最坏情况时间复杂度为 O(n^2)，但在数据量小的情况下，这种复杂度不是问题。此外，插入排序是稳定的，可以保持等值元素的相对顺序。
/// This is a helper function for the sort routine.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);} elsestd::__insertion_sort(__first, __last, __comp);}
好文推荐
你好，我是阿秀，普通学校毕业，校招时拿到字节跳动SP、百度、华为、农业银行等6个互联网中大厂offer，这是我在校期间的编程学习之路，详细记录了我是如何自学技术以应对第二年的校招秋招的。
毕业后我先于抖音部门担任全栈开发工程师，目前在上海某外企带领团队继续从事全栈开发，负责的项目已经顺利盈利300w+。在研三那年就组建了一个阿秀的学习圈，一直持续分享校招/社招跳槽找工作的经验，都是自己一路走过来的经验，目前已经累计服务超过 4200 +人，欢迎点此了解一二。
