求时间复杂度为O(log n)的并行排序算法伪代码

首先明确：基于比较的排序无法在O(log n)的并行时间内完成——这类排序的总运算量下界是Ω(n log n)，即使有无限多处理器，由于比较操作的依赖关系（比如要确定a、b、c的顺序，必须先完成a&b、b&c的比较才能推导a&c的关系），最长依赖链（跨度）的下界是Ω(log n)，但目前没有实用的基于比较的算法能达到O(log n)的跨度，已知最优的实用算法（如并行归并排序、样本排序）跨度为O(log²n)。

但如果允许非比较类排序（比如基数排序），在PRAM等理想并行模型下，当元素的键长度为O(log n)时，可以实现跨度为O(log n)的并行排序。这类算法利用位运算的并行性，每一轮处理一位，通过前缀和并行计算元素的目标位置，最终完成排序。

你提到的快速排序和选择排序都是基于比较的算法：

• 并行快速排序的跨度为O(log²n)，总运算量O(n log n)；
• 选择排序的并行版本几乎没有性能提升，跨度仍为O(n)，显然不符合需求。

并行基数排序伪代码（跨度O(log n)） #

假设待排序数组A包含n个元素，每个元素是k位二进制数，且k=log n（保证总跨度为O(log n)），使用PRAM模型的并发读写能力：

// 并行基数排序
function ParallelRadixSort(A, n):
    // 从最低位到最高位依次处理每一位
    for d from 0 to k-1:
        // 1. 并行统计当前位为0和1的元素数量
        count0 = 0, count1 = 0
        parallel for i from 0 to n-1:
            if (A[i] >> d) & 1 == 0:
                count0 += 1
            else:
                count1 += 1
        
        // 2. 并行计算每个元素的目标位置（需原子操作保证并发安全）
        pos0 = 0, pos1 = count0
        parallel for i from 0 to n-1:
            if (A[i] >> d) & 1 == 0:
                temp[pos0] = A[i]
                atomic_increment(pos0)
            else:
                temp[pos1] = A[i]
                atomic_increment(pos1)
        
        // 3. 并行将temp数组复制回A
        parallel for i from 0 to n-1:
            A[i] = temp[i]
    return A

说明： #

• 每一轮循环的操作都是并行执行的，统计计数、位置计算、数组复制的跨度均为O(1)；
• 总共执行k=log n轮，因此总跨度为O(log n)；
• 实际实现中也可以用前缀和算法替代原子递增，更高效地计算目标位置，避免并发冲突。

内容的提问来源于stack exchange，提问作者Astroguy