谈谈 STL 中的 std::sort | 始终

[Liam0205]

https://liam.page/2018/09/18/std-sort-in-STL/

前些天在 Bilibili 上看到一个视频（6 分钟演示 15 种排序算法）。好事者戏称：「在视频中，你能听到：冒泡咕噜声、飞机坠地声、暖瓶灌水声、猴子乱叫声等等」，实在搞笑得很。 C++ 的标准模板库有一个很霸气的解读：「标准模板库里的任意算法、数据结构，你找不到一个实现，在所有的情况下都优于标准模板库的实现；否则，它就应该进入标准模板库」。因此，对于排序问题来说，C++ 里的标准模板库中的 s

[jackymxp]

写的很好，有一点疑问：

1. 因递归切分，导致 last - first <= __stl_threshold 而切换成插入排序，调用插入排序final_insertion_sort，直接走else分支吧，调用insertion_sort，这个就是不用做检查的那种插入排序吧。

所以对于这个分支的分析，是否有误，帮判断一下。

[Liam0205]

@jackymxp 写的很好，有一点疑问：

1. 因递归切分，导致 last - first <= __stl_threshold 而切换成插入排序，调用插入排序final_insertion_sort，直接走else分支吧，调用insertion_sort，这个就是不用做检查的那种插入排序吧。

所以对于这个分支的分析，是否有误，帮判断一下。

这里说的是 __introsort_loop 的退出条件。它退出之后，调用 final_insertion_sort，然后调用 insertion_sort。