几乎所有的编程语言都会提供排序函数，比如C语言中qsort()、C++STL中的sort()、stable_sort()，还有Java语言中的Collections.sort()。在平时开发中我们一般也都是直接使用它们了，那这些底层具体是怎么实现的呢？
基于这个问题，我们来讨论讨论：如何实现一个通用的、高性能的排序函数。
如何选择合适的排序算法？
我们先来回顾一下：
我们前面讲过，当数据规模比较小的时候，可以选择O(n^2)复杂度的算法，如果数据规模比较大，则用复杂度为O(nlogn)的算法效率会更高。实际上，我们使用归并排序的情况并不多。前面说过，归并排序并不是一个原地排序算法，它会另外占用内存空间。所以，当空间有限时，我们会优先使用快速排序。然而，对于快排，在最坏的情况的情况下，它的时间复杂度会退化到O(n^2)，对于这个问题我们应该解决呢？
如何优化快速排序？
其实，从之前讲快排的这篇文章：中我们可以发现，时间复杂度退化是因为，当原来序列趋近或者就是有序的，而我们的分区点又选择了最后一个元素。所以，对于复杂度的退化问题，我们可以通过 选择合适的分区点来解决。
那么怎样的分区点是好的分区点或者说如何选择分区点呢？
最理想的分区点是：被区分点分开的两个分区中，数量差不多。下面是几个比较常用、比较简单的分区算法：
- 三数取中法
我们从区间的首、尾、中间分别取出一个数，然后比较大小，取 这3个数的中间值作为分区点。当然，如果数据量比较大，那可能要采用“五数取中”或者“十数曲中”的方法了。 - 随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法虽然不能保证每次分区点选的好，但是和从概率的角度来看，也不大可能每次都选的很差:)。
我们知道，快排是用递归来实现的。这篇文章：10-递归：如何用三行代码找到最终推荐人？中有讲到，当用递归时要警惕堆栈溢出。为了避免快排里递归过深而堆栈过小导致堆栈溢出，有两种解决办法：第一种就是文章中的限制递归深度，第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。
举例分析排序函数
为了加深印象，我们用Glibc中的qsort()函数举例说明一下。
虽然从名字看上去很像是基于快速排序算法实现的，我们可以想象的到，一个通用的算法往往不止一种「基排序」算法。事实上也确实不止一种。
看了源码我们会知道，qsort()会优先使用归并排序输入数据，虽然它的空间复杂度并不是O(1)，但是对于小数据量的排序，问题也不大。如果数据量太大，那肯定就不能用归并来排了，这时qsort()就会改用快速排序来排序。
那qsort()中是如何去分区点的呢？如果看看源码我们就知道，它使用的方法就是“三点取中”法。对于递归中堆栈溢出的问题，qsort()就是通过自己实现一个堆上的栈，手动模拟递归来解决的。
实际上，qsort()并不仅仅用到了归并和快排，它还用到了插入排序。在快速排序中，当要排序的区间元素的个数小于等于4，qsort()就会退化成插入排序，不再继续用递归来做快速排序。
内容小结
通过分析如何实现一个工业级通用的、高效的排序函数，将前面几篇文章中讲的排序算法串了起来。大部分的排序函数都是采用O(nlogn)排序算法来实现，但是为了尽可能的提高性能会做很多的优化。
我们还讲了快速排序的优化策略，如何合理的选区分区点、避免递归太深导致堆栈溢出这样的问题。
课后思考
能否分析一下你所熟悉的语言中的排序函数都是用什么排序算法实现的呢？
@Liam
查看了下Arrays.sort的源码，主要采用TimSort算法, 大致思路是这样的：
1、元素个数 < 32, 采用二分查找插入排序(Binary Sort)
2、元素个数 >= 32, 采用归并排序，归并的核心是分区(Run)
3、找连续升或降的序列作为分区，分区最终被调整为升序后压入栈
4、如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阙值
5、每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并
6、最终栈内的分区被全部合并，得到一个排序好的数组
Timsort的合并算法非常巧妙：
1、找出左分区最后一个元素(最大)及在右分区的位置
2、找出右分区第一个元素(最小)及在左分区的位置
3、仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的
有问题？发送 issues 给我~