排序是计算机科学的基础，几乎出现在每场技术面试中。此题考察你对算法设计权衡的理解：时间复杂度、空间复杂度、稳定性和实际性能考量。
涵盖主要算法：快排、归并排序、堆排序，以及插入排序作为补充。
对比时间复杂度：每种算法的最好、平均和最坏情况。
讨论稳定性（归并稳定，快排不稳定）及其重要性。
解释实际考量：缓存性能、原地排序、简单算法何时更优。
快排平均 O(n log n)，空间 O(log n)，其缓存友好的访问模式使其在实践中最快——大多数语言标准库都用它或其混合版本。最坏情况 O(n²)，但随机化选择枢轴使其极不可能发生。归并排序在所有情况下保证 O(n log n) 且是稳定的，适合需要保持顺序的场景或链表排序。它需要 O(n) 额外空间。堆排序原地 O(n log n) 但缓存性能差。对于小数组或近乎有序的数组，插入排序的 O(n) 最优情况和低开销使其比任何分治算法都快——所以 TimSort（Python、Java）在归并中对小段用插入排序。通用内存排序我选快排，需要稳定性或外部排序选归并，小数组或混合策略中用插入排序。
了解实际库使用混合排序：TimSort（归并+插入）、IntroSort（快排+堆排序）。
稳定性在多关键字排序时很重要——一定要提到。
准备好解释为什么快排实际上比归并快，尽管归并最坏情况更好。
稳定排序保持相等元素的相对顺序。归并排序和插入排序是稳定的；快排和堆排序不是。
快排顺序访问内存，对缓存友好。常数因子更低，且原地排序避免了内存分配开销。
没有唯一最好的。通用场景下 TimSort 等混合算法表现最佳。正确选择取决于数据规模、是否需要稳定性和内存限制。