任意分布数据的映射归并排序算法研究

The New Merging Sort Algorithm by Mapping

针对银行业务管理、高考成绩统计、气象资料整理等一类特殊“汇总”排序问题 .文中提出了一种以映射、链接和归并为基础的新排序算法映射归并排序算法 (以下简称为“映射归并排序”) ,给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果 .算法分析和实验结果都表明 :映射归并排序方法和待排序数据分布无关 ,其时间复杂度仅为O(N) ;而且在处理上述大规模“汇总”排序问题时 ,映射归并排序速度明显优于FlashSort、ProportionSplitSort、2 路重复的K路归并排序和直接K路归并排序等算法 .

This paper presents a new sorting method, the merging sort algorithm by mapping, which consists of mapping,linking and merging. The algorithm description, the time complexity and the experimental results in C language are also given in this paper. The algorithm analysis and experimental results show that the time complexity is O(N), which is not related to the data distribution. The method is obviously better than those of Flash Sort、Proportion Split Sort、2 Course Merging Sort and Straight K Course Merging Sort in dealing with the sorting problem of large scale gathering.