Dual Pivot Quick Sort
夫神提到CF一题sort 8W多个数据TLE，要Shuffle才能过。于是开始再次研究QSort
Arrays.sort 其实是Dual pivot QSort，作者戳 http://iaroslavski.narod.ru/
他做出的贡献是对于qsort里 swap的平均操作次数从nlogn降到了0.8nlogn，并给出证明 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf,
而compare次数不变，并且对于许多普通单pivot的QSort会最坏复杂度的情况， 该算法都不会出现最坏复杂度。
但是他的缺点依然是最坏ON^2没有避免。正如最后一个数据TLE一样。
没有看STL源码剖析一直是遗憾，老早的read list一直拖到现在，今天找到这篇博客 http://feihu.me/blog/2014/sgi-std-sort/#comment-1922883630
瞬间豁然开朗，其实解决方案就是混合sort，这也是我们没有纯粹原创方法的解决方案之一，heap sort既然常数因子比较大，而且没有利用局部性原理 http://www.zhihu.com/question/20842649
所以qsort多数情况比他快，但是QSort最坏n^2一直没有解决，那么何不综合二者有点呢，设置递归深度，如果达到一定深度，就heapsort。这是introsort最核心的算法。http://en.wikipedia.org/wiki/Introsort
但是谈到具体细节，还有很多值得推敲的，比如insertion sort怎么优化，快排怎么用while+一次递归调用来减少函数调用次数设置的递归深度阈值是2*lower_upper(logn),
因为平均是logn递归调用，最坏n，如何找到这之间的一个阈值也是一门学问，以及16个元素作为insertion和qsort之间的阈值，(dual pivot qsort 是17)
具体细节还看这篇饕餮盛宴！http://feihu.me/blog/2014/sgi-std-sort/#comment-1922883630
源码在stl_algo.h中