Cod sursa(job #551785)
#include <fstream>
#include <string.h>
using namespace std;
int i,N,start;
int v[500001],x[500001];
inline void radix(int byte,int a[],int b[])
{
int i;
int cnt[256],ind[256];
memset(cnt,0,sizeof(cnt));
memset(ind,0,sizeof(ind));
for(i=start;i<N;i++) cnt[(a[i]>>byte)&255]++;
for(i=1;i<256;i++) ind[i]=ind[i-1]+cnt[i-1];
for(i=start;i<N;i++) b[ind[(a[i]>>byte)&255]++]=a[i];
if(byte!=24)
for(i=start;i<N;i++)
if(b[i]>=(1<<(byte+8)))
{
start=i;
break;
}
}
int main()
{
ifstream in("algsort.in");
ofstream out("algsort.out");
in>>N;
for(i=0;i<N;i++) in>>v[i];
start=0;
radix(0,v,x);
radix(8,x,v);
radix(16,v,x);
radix(24,x,v);
for(i=0;i<N-1;i++) out<<v[i]<<' ';
out<<v[N-1]<<'\n';
return 0;
}