Linux sort工具为何采用归并排序而非线性复杂度排序算法？

• 线性排序的适用场景太窄：基数排序、计数排序都不是通用排序算法。计数排序要求待排序数据是有限范围内的整数，基数排序依赖数据能按固定基数拆分（比如十进制数字）。但Linux sort要处理的是任意文本、字符串、浮点数、带符号数值等各种数据，这些场景下线性排序要么无法直接用，要么改造的复杂度远高于归并排序。

• 理论复杂度≠实际性能：O(n)是理论最优，但实际运行要考虑常数开销。基数排序需要多次遍历数据，处理字符串时还要应对变长、UTF-8编码等问题，每一步的内存IO和操作开销可能比O(n log n)的归并排序更高。而且归并排序的内存访问模式更友好，适配磁盘和内存的分页调度——尤其是sort经常要处理超出内存的大文件（外部排序场景），归并排序的分治思路天然适合分块读写磁盘，线性排序在这种场景下几乎没法高效实现。

• 内存占用的实际限制：就算现代设备内存大，sort可能要处理几十GB甚至上百GB的超大文件。此时线性排序需要的额外内存（比如计数排序的计数数组、基数排序的桶）会随数据规模成比例增长，反而容易超出内存上限。而归并排序可以分块处理，每块只占部分内存，剩余数据存磁盘，内存利用率更灵活。

• 通用性与稳定性的平衡：归并排序是稳定排序，且比较逻辑可以灵活自定义——比如支持-k指定列、-r逆序、-n数值排序等各种规则。线性排序算法很难适配这么多复杂的排序需求，要么需要大量改造，要么根本无法支持。

内容的提问来源于stack exchange，提问作者Tymofii Polischuk