地址映射外分类算法的研究

Research on Address-mapping External Sorting Algorithm

提出一种新的外分类算法,该算法无须预先产生初始归并段,可以快速获得预定分类结果。在特定的数据和硬件配置下,其性能优于二路平衡归并法和二路多步归并法。分析该算法的存储空间开销,给出算法正确性证明,在PC/586上用C++语言对其进行实现。

This paper proposes a new external sorting algorithm. The algorithm need not to produce original merged segment in advance and can immediately get the anticipant sorting result. Under the particular data and hardware configure, the performance of this algorithm exceeds two-ways balance mergesort and two-ways many steps mergesort. It analyzes the memory space spending of this algorithm, proves its correctness and realizes it in C＋＋ on PC/586.