资 源 简 介
应用背景外部排序是一个类排序算法，可以处理大量的数据。外部排序时，需要做数据排序不适合在主存储器的计算设备（通常是内存），相反，他们必须驻留在较慢的外部存储器（通常一个硬盘驱动器）。外部排序通常采用混合排序合并策略。在排序阶段，数据块足够小在主内存中进行读取、排序和写入到一个临时的文件。在合并阶段，排序的子文件合并成一个单一的较大文件。关键技术大多数外部排序例程是基于归并排序。他们通常打破一个大的数据文件转化为一个较短的，排序的运行。这些可以通过反复读取数据文件中的一段数据，生成内存，它与普通的快速排序，排序，排序后的数据写入磁盘。经过排序的运行已产生，一个合并算法是用来将排序文件组合成更长的排序文件。最简单的方案是使用双向合并：合并排序2排序文件到一个文件，然后合并2等等，直到有一个大的排序文件。一个更好的计划是一种多路归并算法：它可能合并也许128更短的运行起来。
