基于LARPBS模型的快速并行归并排序算法  

A fast parallel merge sorting algorithm based on LARPBS model

作　　者：陈宏建[1] 陈峻[1] 吕为[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《扬州大学学报（自然科学版）》2005年第3期1-5,共5页Journal of Yangzhou University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60473012);国家高性能计算基金资助项目(00219);江苏省教育厅自然科学基金资助项目(99KJB520003);扬州大学科研基金资助项目(KK0413161)

摘　　要：提出了一种基于LARPBS模型上的并行归并排序算法,该算法使用M1+ε(0<ε<1)个处理器可以在O(lb lbM)时间内对Mε个有序序列进行归并.利用该归并算法对长度为N的序列进行排序,使用N1+ε个处理器可以在O((lb lb N)2)时间内完成.In this paper a fast parallel merge sorting algorithm based on LARPBS is presented. This method uses M^1＋ε（0〈ε〈1） processors to merge the M^ε sorted sequence in O（lb lb M） time. With this merge algorithm, N^1＋ε processors can be used to sort N elements in O（（lh lb N）^2） time.

关 键 词：光总线 LARPBS模型 归并排序 并行算法 

分 类 号：O141.3[理学—数学] TP301.6[理学—基础数学]