合并选择算法及其并行化

本文基于EMRGESORT算法的思想设计出求顺序统计问题的合并选择算法,串行算法的最坏时间复杂度为θ(nlogk),其中n为问题的大小,k为所找元素的序号。在串行算法之后,在SIMD的树型机器上又给出了算法并行化,并行算法的运实时间为θ(klogn),处理器的总数目为2(n/k)-1。