对于普通的基于比较排序我们拥有一个复杂度下界 \(O(n\log n)\)，然而如果我们允许并行计算的话，将得到一些复杂度更优秀的计算方法。
听到并行这个词许多人就会认为你有几个线程复杂度就除以几，所以线程堆得越多越好。但许多的算法问题都必须要满足你必须要算完 A 才能去计算 B，比如对于普通的前缀和算法，每一个位置的结果都依赖上一个位置，如果直接并行将不会对复杂度产生优化。所以一但允许并行我们还要重新去设计一些算法，此时我们更少地去关心计算网络的大小而是更多地去关心它的深度，一些原本不太优秀的算法在并行计算这方面表现得更加优秀。
OI 甚至 CP 中考察并行算法的题目并不多见，比如说这道考察了计算并行环三染色。
双调排序算法
定义一个序列是双调的，当且仅当它能够分成一个非严格单调递增的前缀和非严格单调递减的后缀（即“单峰”），或者说序列经过循环移位后满足前面的条件
奇偶归并算法
#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;
}