面对可用内存仅 4G，而待排序数据量达 500G 的情形，你会采用何种排序方案？请阐释具体实现步骤与核心算法。

回答思路

1. 【回答框架 1】采用外部排序，核心是归并排序思想。将 500G 数据分块读入内存，每块大小远小于 4G，比如 1G，排序后写回磁盘，形成若干有序子文件。
2. 【回答框架 2】外部排序主要开销在磁盘 I/O，需尽量减少归并趟数。可先进行多路归并，每趟归并尽可能多的有序子文件，利用败者树或堆优化多路归并选择最小元素的过程。
3. 【回答框架 3】内存中需分配输入缓冲区、输出缓冲区。合理设置缓冲区大小，平衡内存使用与 I/O 次数。也可考虑使用置换-选择排序生成更长的初始归并段，减少归并趟数。
4. 【回答框架 4】若数据带有特定规律或可分布式处理，也可考虑哈希分片后并行归并，但需额外考虑分布式环境中的网络传输开销与容错。单机场景下外部归并排序是基本方案。
5. 【回答框架 5】需精确评估磁盘空间需求，排序过程可能需要原数据一倍以上的临时空间，确保磁盘足够。
6. 【关键点 1】外部排序基于归并排序，将大文件分解为可载入内存的块并排序。
7. 【关键点 2】使用多路归并和败者树降低 I/O 次数，提升效率。
8. 【关键点 3】置换-选择排序可生成更长的初始归并段，减少归并轮次。
9. 【关键点 4】内存主要用于输入输出缓冲，合理分配是关键。
10. 【关键点 5】最终复杂度受磁盘 I/O 主导，算法时间复杂度可近似为 O(n log n)，但实际瓶颈在磁盘。
11. 【易错点 1】忽视磁盘 I/O 而只关注 CPU 排序时间，导致实际性能差。
12. 【易错点 2】归并路数过少导致磁盘读写过多。
13. 【易错点 3】错误计算临时磁盘空间，导致排序中途磁盘不足。