数据结构预算法文件与外排序

### 数据结构中的外部排序

#### 外部排序概述
外部排序是指用于处理无法全部加载到内存的大规模数据集的排序方法。对于含有 n 个记录的数据文件，如果其容量远大于内部存储器的容量，则需采用特定策略来完成排序工作[^1]。

#### 使用归并排序实现外部排序
最常用的外部排序技术基于归并排序的思想。具体过程如下：

每次仅能加载两部分待合并的数据至内存中；从这两部分选出最小的 m 项存入缓存区。一旦缓存满载便立即将这些已排序项目回写至磁盘上新的位置。接着再对比剩下未处理的关键字值大小关系，倘若某一部分数据已被完全取出则应立即自磁盘读取下一组数据进入内存继续操作直至所有子序列都按序排列完毕为止。

def external_merge_sort(input_file, output_file, buffer_size):
    # Step 1: Split input file into smaller chunks that fit in memory and sort them individually.
    chunk_files = []
    
    with open(input_file, 'r') as f_in:
        while True:
            lines = list(islice(f_in, buffer_size))
            if not lines:
                break
            
            sorted_lines = sorted(lines)
            
            temp_chunk = tempfile.NamedTemporaryFile(delete=False)
            temp_chunk.write(''.join(sorted_lines).encode())
            temp_chunk.close()
            chunk_files.append(temp_chunk.name)

    # Step 2: Merge the sorted chunks using a k-way merge algorithm (k=number of chunks).
    with open(output_file, 'w') as f_out:
        heap = []

        for i, filename in enumerate(chunk_files):
            iterator = iter(open(filename, 'rb'))
            try:
                item = next(iterator).decode().strip()
                heapq.heappush(heap, (item, i, iterator))
            except StopIteration:
                pass
        
        while heap:
            smallest_item, idx, it = heapq.heappop(heap)
            f_out.write(smallest_item + '\n')
            
            try:
                new_item = next(it).decode().strip()
                heapq.heappush(heap, (new_item, idx, it))
            except StopIteration:
                continue
                
        for fn in chunk_files:
            os.remove(fn)

此代码片段展示了如何对外部大文件执行二路归并排序的过程。首先把原始输入分割成多个适合内存的小块分别独立排序后保存下来作为临时中间产物；之后运用堆这种优先队列结构辅助完成多路归并最终得到全局有序的结果输出给定的目标文档内。