双调排序(Bitonic Sort)

双调排序(Bitonic Sort)是一种基于排序网络的并行排序算法,由肯尼思·巴彻在上世纪六十年代提出。它的比较与交换操作序列完全固定、与输入数据无关,因此天然适合在 GPU、FPGA 等并行硬件上批量执行。

概述

所谓双调序列,是指一个先单调递增再单调递减(或经过循环移位后如此)的序列。双调排序的核心在于双调归并:任何双调序列都可以通过一系列固定位置的比较交换,被拆分为两个更短的双调序列并各自有序化。算法先把任意输入逐层构造成双调序列,再反复归并直到整体有序。

核心特点

• 属于数据无关的排序网络,比较位置在编译期即可确定,便于流水线与向量化。
• 对长度为 n 的序列,网络深度约为对数平方级,总比较次数约为 n 乘以对数平方级。
• 每一层内部的比较相互独立,可完全并行执行,并行时间复杂度为对数平方级。
• 通常要求输入长度为二的幂,否则需填充哨兵元素补齐。

应用场景

双调排序广泛用于 GPU 通用计算中的排序原语,许多图形与深度学习框架的底层排序基于它或其变体。它也用于硬件排序电路、网络交换设备中的分组调度,以及需要固定时序、抗侧信道的场合。当数据量适中且并行资源丰富时,它常比串行的快速排序更快。

常见问题

问:双调排序的总比较次数比快速排序多,为什么还用它?答:虽然其总比较次数高于线性对数级的串行算法,但由于每层比较可完全并行,在拥有大量并行单元的硬件上,实际墙钟时间反而更短。

问:为什么输入长度常要求是二的幂?答:双调网络的递归拆分依赖对半划分,长度为二的幂时结构最规整;非二的幂长度需用极大或极小值填充到最近的二的幂后再排序。