排序算法专题：从 TimSort 到并行排序
💡
原文中文，约1700字，阅读约需4分钟。
📝
内容提要
选择排序算法应根据数据特性和需求。推荐的阅读顺序为：TimSort、pdqsort、基数排序、外部排序、并行排序和排序基准测试。理解每种算法的优缺点有助于提升性能。
🎯
关键要点
-
选择排序算法应根据数据特性和需求。
-
推荐的阅读顺序为：TimSort、pdqsort、基数排序、外部排序、并行排序和排序基准测试。
-
理解每种算法的优缺点有助于提升性能。
-
TimSort适合想理解标准库默认排序设计的读者。
-
pdqsort适合想了解现代默认排序的读者。
-
基数排序适合想判断O(n)排序适用场景的读者。
-
排序基准测试适合想直接看数据的人。
-
外部排序在数据装不进内存时，I/O模型主导性能。
-
并行排序需要重新考虑同步、分片和吞吐。
-
如果需要稳定排序且数据常常部分有序，优先看TimSort。
-
如果需要通用内存内排序且不要求稳定性，优先看pdqsort。
-
如果数据规模大且键提取便宜，再考虑基数排序。
-
如果数据不在内存里，直接看外部排序。
-
如果瓶颈在并行吞吐，再看并行排序。
-
排序基准测试能提供实测数据以支持选型。
❓
延伸问答
选择排序算法时应该考虑哪些因素？
选择排序算法应根据数据特性、稳定性需求、内存容量、瓶颈位置（CPU或I/O）以及单线程或多核环境来决定。
TimSort适合什么样的排序需求？
TimSort适合需要稳定排序且数据常常部分有序的场景。
pdqsort与其他排序算法相比有什么优势？
pdqsort适合通用内存内排序且不要求稳定性，代表了现代不稳定默认排序的主流工程答案。
基数排序在什么情况下最有效？
基数排序在数据规模大且键提取便宜的情况下最有效。
外部排序的主要考虑因素是什么？
外部排序主要考虑在数据装不进内存时，I/O模型主导性能。
并行排序需要注意哪些问题？
并行排序需要重新考虑同步、分片和吞吐等问题。
➡️
