外部排序是处理大数据的重要技术，特别是在内存有限的情况下。其核心思想是分而治之和多路归并，主要包括生成初始有序run和多路归并两个阶段。外部存储模型强调I/O复杂度，优化I/O次数至关重要。替换选择法可以生成更长的run，但在现代硬件上，简单的内部排序法更高效。败者树在多路归并中表现优越，能有效减少比较次数。随着SSD的普及，外部排序的设计也在不断演进。

多路归并算法利用最小堆高效合并多个已排序数组。将每个数组的最小元素加入堆，提取全局最小值并继续处理，直至所有元素处理完毕。该方法适用于合并K个升序链表，最终返回一个有序链表。