golang 标准库实现简记

sort

大体思路是：

• 先算出 logN，在递归次数不超过 logN 的情况下，数据量大一点使用快排，数据量小一点使用希尔排序。
• 快排本身取 Pivot 哨兵时不采用随机取，而是用 Tukey’s ninther 算法取数组中位数。
• 当递归次数超过 logN 时，这种数据分布一般就是基本有序的。比如Leetcode 912.排序数组最后的几个测试用例，全 2 或者倒序，快排会达到$O(N^2)$的时间复杂度。这时对当前数组进行堆排序。

以上参考自
https://boilingfrog.github.io/2022/03/06/go中的sort包/