TikTok 哪种排序更快：稳定性、数据分布与内存约束

题目重点：不把快排当统一答案，比较归并、堆、插入与非比较排序，并设计公平基准。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

先问n、key比较成本、已排序程度、重复值、是否需稳定、内存预算与是否外存；“最快”不是一个只靠算法名称就能回答的指标。
归并排序最坏O(n log n)，常见实现需O(n)缓冲，稳定且适合流式外部归并；堆排序最坏同界、数组工作空间可O(1)，但一般不稳定且局部性可能较差。
快排良好pivot时平均O(n log n)，最坏O(n²)，常见实现不稳定；随机化/三路划分分别应对对抗顺序/大量重复，introspective策略可以在深度过大时切换堆排序。
插入排序O(n²)最坏，但小n或少量逆序时低开销，已排序可线性。计数/基数排序借助有限整数或数字位假设绕开一般比较下界，需计值域/位数与额外空间。
对象排序还要看key计算次数、缓存、分配与解释器实现；用一次key预计算常能比反复比较中执行昂贵逻辑更有意义。语言内置排序经工程优化，不应拿手写理论常数直接断言更快。
基准生成代表分布：随机、升序、降序、大量重复、近有序、昂贵key；检查稳定性与结果后计多轮分位耗时，区分复制/生成数据与排序成本，不能单个小样本下结论。

订单按金额排序但需保留同金额时间顺序，应选稳定合同；百万外存记录不能用需要全量RAM的方案硬套。十几项数组可能插入排序优于复杂结构，其结论需在实际环境验证。

一般比较排序最坏下界Ω(n log n)，限定输入可更低；各算法时间与辅助空间必须同时报告。外存成本更看块IO，不只CPU比较次数。