#define UL unsigned long int
void reservemaine(UL *d,UL *e,UL *td,UL *te,UL l,UL r,bool totemp)
{
UL i,j;
UL center;
center=(double)(r-l)/2+0.5;
center+=l;
UL pivotdata=d[center];
UL leftpos,rightpos,centerpos;
UL leftcount=0,centercount=0,rightcount=0;
if (l>=r) return;
////数をカウント
for(i=l;i<=r;i++)
{
if (d[i]<pivotdata)
{
leftcount++;
}
if (d[i]==pivotdata)
{
centercount++;
}
if (d[i]>pivotdata)
{
rightcount++;
}
}
// < = > の各格納開始位置を計算
leftpos=l;centerpos=l+leftcount;rightpos=r-rightcount+1;
//データのコピー
for(i=l;i<=r;i++)
{
if (d[i]<pivotdata)
{
td[leftpos]=d[i];te[leftpos]=e[i];leftpos++;
}
if (d[i]==pivotdata)
{
td[centerpos]=d[i];te[centerpos]=e[i];centerpos++;
}
if (d[i]>pivotdata)
{
td[rightpos]=d[i];te[rightpos]=e[i];rightpos++;
}
}
//テンポラリーに基準値のデータがある場合は、メイン配列にコピーする
if (totemp)
{
for(i=l+leftcount;i<l+leftcount+centercount;i++)
{
d[i]=td[i];e[i]=te[i];
}
}
if (leftcount>1)
{
reservemaine(td,te,d,e,l,l+leftcount-1,!totemp);
}else
{//小さいデータが一つなら、確定
if (totemp)
{
d[l]=td[l];e[l]=te[l];
}
}
if (rightcount>1)
{
reservemaine(td,te,d,e,r-rightcount+1,r,!totemp);
}else
{//大きいデータが一つなら、確定
if (totemp)
{
d[r]=td[r];e[r]=te[r];
}
}
}
void reservesorte(UL *d,UL *e,UL count)
{
UL *td,*te;
if (count<2) return;
td=(UL*)malloc(sizeof(UL)*count);
te=(UL*)malloc(sizeof(UL)*count);
reservemaine(d,e,td,te,0,count-1,true);
free( te );
free( td );
}