#include<stdio.h>
#include<algorithm>
using namespace std;

void InsertionSort(int a[],int N)
{
	int j,p,tmp;

	for(p=1;p<N;p++)
	{
		//1-N-1趟目标
		tmp=a[p];
		for(j=p;j>0 && a[j-1]>tmp;j--)
		{
			a[j]=a[j-1];
		}
		a[j]=tmp;
	}
}



int median3(int a[],int left,int right)
{
	int mid=(left+right)/2;

	if(a[left]>a[mid]) swap(a[left],a[mid]);
	if(a[left]>a[right]) swap(a[left],a[right]);
	if(a[mid]>a[right]) swap(a[mid],a[right]);

	swap(a[mid],a[right-1]);

	return a[right-1];
}

const int cutoff=3;

void Qsort(int a[],int left,int right)
{
	int pivot,i,j;

	//左小右
	if(left+cutoff<=right)
	{
		//三数取中
		pivot=median3(a,left,right);
		i=left;j=right-1;

		//切割
		for(;;)
		{
			while(a[++i]<pivot){}
			while(a[--j]>pivot){}
			if(i<j)
				swap(a[i],a[j]);
			else
				break;
		}

		//换回轴枢
		swap(a[i],a[right-1]);

		Qsort(a,left,i-1);
		Qsort(a,i+1,right);
	}
	else
		InsertionSort(a+left,right-left+1);
}

void main()
{
	int a[13]={13,12,11,10,9,8,7,6,5,4,3,2,1};
	Qsort(a,0,12);
	return ;
}