对于普通的基于比较排序我们拥有一个复杂度下界 \(O(n\log n)\)，然而如果我们允许并行计算的话，将得到一些复杂度更优秀的计算方法。
听到并行这个词许多人就会认为你有几个线程复杂度就除以几，所以线程堆得越多越好。但许多的算法问题都必须要满足你必须要算完 A 才能去计算 B，比如对于普通的前缀和算法，每一个位置的结果都依赖上一个位置，如果直接并行将不会对复杂度产生优化。所以一但允许并行我们还要重新去设计一些算法，此时我们更少地去关心计算网络的大小而是更多地去关心它的深度，一些原本不太优秀的算法在并行计算这方面表现得更加优秀。
OI 甚至 CP 中考察并行算法的题目并不多见，比如说这道考察了计算并行环三染色问题。
研究并行排序时，我们也同时会研究排序网络。排序网络问题与并行排序问题十分有关联性，因为许多排序网络更浅的算法更加易于并行。排序网络指得是不依赖排序数组具体的取值，只允许你使用比较器构造出一个操作序列，满足任意一个序列经过这些操作后都变得有序。比较器的操作定义为如果 \(a_x<a_y\) 则交换 \(a_x,a_y\) 的取值。一个排序网络的深度指的是如果相邻的若干次操作如果互不相干就可以划分到同一层那么它的最小层数，这直接影响了该排序网络的并行复杂度。冒泡排序算法可以直接建出一个大小为 \(O(n^2)\) 深度 \(O(n^2)\) 的网络，如果修改成对奇偶位置分别冒泡则可以做到深度为 \(O(n)\) 级别。
而下面的并行排序算法都是时间复杂度 \(O(n\log^2 n)\)，可以建出深度为 \(O(\log^2 n)\) 的排序网络。这些算法都是分治算法，为了方便起见以下默认将序列长度扩充成 2 的整幂。
双调排序算法
定义一个序列是双调的，当且仅当它能够分成一个非严格单调递增的前缀和非严格单调递减的后缀（即“单峰”），或者说序列经过循环移位后满足前面的条件。
双调排序的基本思路是将原序列排序成双调序列，然后将双调序列再排序成单调序列。
对于如何排序成双调序列，思路十分暴力：将原序列折成两半，前面一半递归用双调排序将排成递增序列，后面一半也双调排成递减序列。
而双调排序的骄傲之处在于，对于一个双调序列，我们可以只使用 \(O(\log n)\) 层比较器将其归并成一个单调序列。
有这么一个 Batcher 定理，它指出了如果将双调序列劈成两半，对应位置（即 \(i\) 与 \(i+\frac{n}{2}\)）使用一次比较器后，原序列将对半分成两个双调序列，而且两边的值域不相交。那么我们只需要直接往两边递归下去就可以得到一个单调序列了。
奇偶归并算法
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
int read(){/*...*/}
const int INF=0x3f3f3f3f;
int a[1<<20];
void ConditionalSwap(int x,int y,bool fl=0){
if(fl) swap(x,y);
if(a[x]>a[y]) swap(a[x],a[y]);
}
void BitonicChange(int l,int r,bool fl){ //bitonic->monotonic
if(l+1==r) return;
int p=(r-l)>>1;
for(int i=l;i<l+p;++i)
ConditionalSwap(i,i+p,fl);
BitonicChange(l,l+p,fl);
BitonicChange(r-p,r,fl);
}
void BitonicSort(int l,int r,bool fl=0){ //random->bitonic->monotonic
if(l+1==r) return;
int p=(r-l)>>1;
BitonicSort(l,l+p,fl^1);
BitonicSort(r-p,r,fl);
BitonicChange(l,r,fl);
}
void OddEvenMerge(int l,int r,int t){
if(l+t==r) return;
if(l+t+t==r) return ConditionalSwap(l,r-t);
OddEvenMerge(l,r,t<<1);
OddEvenMerge(l+t,r+t,t<<1);
for(int i=l+t;i<r-t;i+=(t<<1)) ConditionalSwap(i,i+t);
}
void OddEvenSort(int l,int r){
if(l+1==r) return;
int p=(r-l)>>1;
OddEvenSort(l,l+p);
OddEvenSort(r-p,r);
OddEvenMerge(l,r,1);
}
int main(){
int len=read();
for(int i=0;i<len;++i) a[i]=read();
int n=1;
while(n<len) n<<=1;
for(int i=len;i<n;++i) a[i]=INF;
OddEvenSort(0,n);
// Or BitonicSort(0,n);
for(int i=0;i<len;++i) printf("%d ",a[i]);
putchar('\n');
return 0;
}