Batcher的合并交换排序

use*_*088 5 sorting algorithm

有没有人对Batcher的Merge-Exchange Sort有很好的指导/解释?

这与Batcher的bitonic排序或Batcher的奇偶合并排序算法不同,尽管许多文章假装它是.

Gar*_*ees 3

Donald Knuth,计算机编程艺术,算法 5.2.2M(第三卷,第 111 页)。

\n\n

Ken Batcher (1968),“排序网络及其应用”,Proc。AFIPS 春季联合计算机会议32:307\xe2\x80\x93314。

\n

  • Knuth 根据网格的重复折叠给出了几何解释(参见第 113 页)。这可能有助于你的直觉。另外,我在我的答案中添加了巴彻的原始论文;如果这不能帮助您,为什么不[问他本人](http://www.cs.kent.edu/~batcher/)? (4认同)