快速合并分类算法的优化

本文介绍一种改进的快速合并分类算法及其在微机上的实现。在用各种比较操作进行分类的算法中,著名的合并分类(Merge Sort)法的分类速度最快,但它要以较大的额外存贮空间为代价。本算法与合并分类法相比,速度更快,而需要的额外存贮空间却减少了50％～67％。实验结果表明,N在500～1500范围内,速度提高了4.7％～8.5％,所需的额外存贮空间减少了51.2％～65.9％。本算法已在IBM PC机上用BASIC语言实现,可把本程序作为一个子程序加以调用。

An Optimization of a Fast Merge Sort Algorithm

This paper describes an improved fast merge sort algorithm and its implementation on a microcomputer.In various of sort algorithms based on comparative operations,the well-known merge sort algorithm is the fastest but at the expense of more extra memory space. In comparison with general merge sort algorithm,this one described in this paper is faster and the extra memory space required is reduced by 50%-67%.It is shown in the experiment with N in the range of 500-1500, it is sped up by 4.7%-8.5% and the extra memory space required, however,was reduced by 51.2% -65.9%.The algorithm has been implemented on IBM PC with BASIC language. The corresponding program can be called as a standard subroutine.