双调排序

以后再说。

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int INF=0x3f3f3f3f;
int a[1<<20];
void ConditionalSwap(int x,int y,bool fl){
	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){ //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);
}
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;
	BitonicSort(0,n,0);
	for(int i=0;i<len;++i) printf("%d ",a[i]);
	putchar('\n');
	return 0;
}