排序题很适合做成一张表：冒泡、选择、插入、归并、快速、堆排序各有复杂度和稳定性。表格能帮人记忆，却不能替调用场景做决定。真正选算法以前，至少要知道数据量、是否需要稳定、能否复制数组，以及比较函数本身有多贵。
插入排序在小规模或接近有序的数据上很有竞争力，因为它的常数开销低，且可以原地处理。选择排序交换次数少，但比较次数仍然是平方级；冒泡排序适合教学，不适合因为名字熟悉就放进业务代码。算法的“适用”从来不是只看平均复杂度。
归并排序给出稳定的 O(n log n)，代价是额外空间和合并过程。它适合需要稳定顺序的场景，例如按多个字段排序时保留原有顺序；外部排序还可以把它扩展到内存放不下的数据。空间是为稳定性和可预测性支付的成本。
快速排序平均表现很好，但最坏情况和枢轴选择有关，递归深度也需要关注。教材里的 filter 版本容易读，却会复制数组、改变空间复杂度，不应拿它的表现去代表原地分区实现。堆排序的额外空间小，但常数和缓存局部性未必最好。
语言内置 sort 也不能被一句“都是 TimSort”概括。不同语言和运行时会采用不同实现，有的对数组类型、稳定性和比较函数有明确保证，有的只保证结果有序。使用前读文档，或者写一个最小测试确认行为，比背算法名称可靠。
我现在会先写约束再选算法：是否必须稳定，是否允许复制，输入是否大致有序，比较函数能否保持传递性。比较器不满足这些条件时，再快的排序也可能产生不可解释的结果。
排序算法的价值不只是面试时说出 O(n log n)。它让人学会把“看起来能用”拆成一组可以验证的条件。条件写清楚以后，内置实现往往就是最好的选择；需要特殊性能时，也知道自己究竟在替什么约束买单。
如果数据来自用户，比较器还要处理空值、大小写、自然排序和本地化规则。先定义这些规则，再谈算法，往往比把一个 O(n log n) 的实现换成另一个更有收益。排序的结果应该能被产品和测试共同描述。
排序的选择还取决于数据从哪里来。内存中的小数组、需要稳定顺序的列表、无法一次装进内存的文件，各自的约束不同；把复杂度表格直接变成“推荐答案”，很容易遗漏比较器成本、额外空间和数据分布。
我现在会先写清排序结果的定义，再选实现。比较器是否传递、空值放前还是放后、相同键是否保留原顺序，这些规则比背下某个算法名称更能避免线上出现难解释的结果。
如果性能真的重要，我会先准备一个固定数据集，记录输入规模、重复比例、是否有序、比较器和运行环境，再比较内置实现与手写实现。一次基准只能说明这组条件，不应该被写成所有数据都适用的结论。
排序结果还需要测试稳定性和边界：空数组、相同键、空值、极端数字和比较器返回相等。算法选择到最后仍然是约束的记录，复杂度只是其中一个维度。