最近看《算法导论》时接触到一个比较有趣的概念：排序网络（sorting networks）。什么是排序网络呢？简单来说，排序网络就是通过一系列的比较器（comparators）来调整输入数据的次序，使无序的数据最终变成有序的输出。
一个很自然的问题是，我们已经有了那么多种排序算法，为什么还需要排序网络呢？个人觉得有以下几个原因。
普通的排序算法，不管是简单的冒泡排序、插入排序，还是效率更高的堆排序、归并排序、快速排序等，都是在串行的计算机上实现的。通过信息论或者决策树模型可以证明，基于比较的排序算法在最坏情况下必须要通过 \(\Omega(n \log n)\) 次比较操作才能完成对 n 的数据的排序。因此，具有平均情况时间复杂度 \(\Theta(n \log n)\) 的排序算法已经是最优的了。虽然桶排序、计数排序等可以实现线性时间的排序，但是它们都依赖于输入数据的某些特殊性质，并非通用的排序算法。那么，如何做到比 \(\Theta(n \log n)\) 时间更快的排序呢？既然所需要的比较操作次数无法减少，那么一个可能的方法就是并行化，在同一时间完成多次比较，排序网络就可以做到这一点。
排序网络的另一个优点是适合于硬件实现。观察一下衡量排序网络性能的网络“深度”，会发现它居然和数字电路中的“关键路径”的概念不谋而合。我们知道关键路径决定了数字电路能够工作的速度，而排序网络的深度也决定了它能够以多快的速度完成排序。
我们先来看一个简单的例子：完成对两个输入数据进行排序的网络。
这个“网络”仅仅由一个比较器组成，如果用数字电路来实现也非常简单，只需要一个比较器和两个多路选择器就能够实现。
有了比较器的基本结构，我们下面就可以构建比较复杂的排序网络了。下面是一个四输入的排序网络结构和排序过程。
（图片来自Wikipedia，作者Oskar Sigvardsson）
其排序原理如下：前面4个比较器使最大的元素和最小的元素分别移动到最底层和最顶层，最后一个比较器用来调整中间两个元素的次序。
那么如何构建一般的对任意个元素进行排序的网络呢？这可以用递归的方法实现。假设我们已经有一个能完成n个元素的排序的网络，其输出为从小到大排列的n的元素，为了实现能够对n+1个元素进行排序的网络，我们可以把第n+1个元素插入到前面n个有序输出中的正确位置，此时得到的就是n+1个元素的有序排列。这实际上就是插入排序的过程。另一种实现n+1个元素排序的方法是首先找出n+1个元素中最大的元素，将它移动到网络的最底层（通过n个比较器），此时问题的大小就被减小为n，然后用同样的方法递归解决问题。这对应的是冒泡排序的过程。这两种网络的结构如下图所示，我们惊讶地发现，这两种网络的结构居然是一样的！
（图片来自Wikipedia，作者Oskar Sigvardsson）
使用上面构造的这种网络来排序n个元素，需要使用n(n-1)/2个比较器，网络的深度（“关键路径”）则是2n-3。那么是否存在效率更高的排序网络呢？答案是肯定的。下面的这种“砖墙”式网络就是对上面网络的一种改进，其正式名称叫做奇偶移项排序网络（Odd-even transposition sorting networks）。它的深度是n。
更进一步，能否利用排序网络实现比线性更加快速的排序呢？答案同样是肯定的。两种常用的高效排序网络是Batcher奇偶归并排序网络（Batcher odd-even merging network）和双调排序网络（Bitonic sorting network）。它们的比较器数量是 \(\Theta(n \log^2 n)\) ，网络深度是 \(\Theta(\log^2 n)\) 。下面是一个8输入的双调排序网络。这里暂不对其详细介绍，感兴趣的读者可以参考《算法导论》第27章。
说到排序网络，一个不得不提到的原理是0-1原理，它是由大名鼎鼎的Stanford计算机科学教授高德纳（Donald Ervin Knuth）提出的。0-1原理证明了如果一个排序网络能够对任意的0-1序列进行正确的排序，那么它能够对由任意数字组成的序列进行正确的排序。非常有趣吧！这真是让我体会到数学之美的定理。
对于我们学微电子的的学生，排序网络更有特殊的意义。它非常容易通过硬件来实现，具有高度的并行性，因而适合完成在芯片中的排序任务，不管是专用的集成电路芯片还是图形处理单元。《GPU Gems 2》这本书中就讲到了排序网络在nVIDIA GPU中的应用。
GPU需要处理大量的数据，而排序是很多数据处理中必要的一步。例如，3D应用程序需要对物体的可见性进行排序，这样才能正确地渲染透明的物体；粒子系统需要按照物体离观察者的远近来进行排序。但是，如果将需要排序的数据从GPU送到CPU进行排序，然后将结果再送回GPU，效率将会很低，无法满足很多实时应用的需求，因此，在GPU中完成排序就成为必需。GPU可以使用大量的运算单元（shader）来进行排序，达到很高的性能。其程序描述需要使用shader language，以后有机会再研究。
其它一些关于排序网络的资料：
Wikipedia上关于排序网络的介绍。
Matrix67的写过一篇非常好的介绍排序网络的文章。