基于图形硬件的双调排序算法优化

摘要

介绍一种新的并行排序算法,该算法以双调归并排序为基础,运用图形硬件的并行体系结构和二叉排序树数据结构的优点,用部分并行代替所有阶段的顺序执行,对双调排序算法进行优化.对该算法进行分析,在理论上n个序列在P个流处理器上的排序,最优的时间复杂度为O((nlogn)/p).实验测试结果表明,优化后的算法比其它基于图形硬件的双调归并排序算法所用时间短.