我正在研究双音排序算法,
我意识到这个算法似乎有两种形式:
维基百科算法 http://en.wikipedia.org/wiki/Bitonic_sorter
替代算法 http://www.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_overview.html (也是 CUDA 示例库中使用的算法)
维基百科算法:
1 2 3 4
d c b a // start
c d a b // compare (1, 2) (3, 4)
b a d c // compare (1, 4) (2, 3)
a b c d // compare (1, 2) (3, 4)
替代算法:
1 2 3 4
d c b a // start
c d a b // compare (1, 2) (3, 4)
a b c d // compare (1, 3) (2, 4)
在这个简单的例子中,替代算法似乎更有效
这两种算法是否等效?
第一个有什么优势吗?