C++,java,Python的sort排序内部实现_c c++ java python sort函数 快速排序

C++

C++内部的sort是由快排，直接插入和堆排序混合的，具体详情见STL源码剖析。

• 数据量大时候先用的快排
• 数据量小时就用直接插入

因为当数据量变小时，快排中的每个部分基本有序，接近直接插入的最好情况的时间复杂度O(n)，就比快排要好一点了。

Java

在Java 6中Arrays.sort()和Collections.sort()使用的是MergeSort，而在Java 7中，内部实现换成了TimSort。
更多细节可以看看这篇博客。但在Java SE7发布后被爆出TimSort的深度bug，吃瓜群众可参考这篇。

之前为什么用 MergeSort？

因为C++模板有很强的inline优化机制，比较操作相对于赋值（移动）操作要快的多（尤其是元素较大时），而java中的情况正好相反，移动（赋值）一般比比较快；另一方面，一般情况下，归并排序的比较次数小于快速排序的比较次数，而移动次数一般多于快速排序的移动次数，二者大约都是2~3倍的差距。因为这样，java标准库中的一般排序使用的归并排序的一种变种。

python

python内部的sort采用的是混合（hybrid）排序：
规模小的时候采用binary insertion
规模大的时候采用samplesort

Reference