#include <stdio.h>
#include <time.h>
#include <algorithm>
#include <random>
#include <x86intrin.h>

void radix(unsigned sdv,int* a,int* b){

	constexpr unsigned mask=0xff;
	unsigned mk[256]={};
	int *pk[256],temp;

	for (int* i=a;i<b;i++){
		mk[(*i>>sdv)&mask]++;
	}
	pk[0]=a;
	for (int i=1;i<256;i++)
		pk[i]=pk[i-1]+mk[i-1];
	for (unsigned i=0;i<256;i++)
	{
		while (mk[i]>0){
			temp=*pk[i];
			unsigned y=((temp)>>sdv)&mask;
			while (y!=i){
				std::swap(temp,*pk[y]);
				pk[y]++;
				mk[y]--;
				y=((temp)>>sdv)&mask;
			}
			*pk[i]=temp;
			pk[i]++;
			mk[i]--;
		}
	};
	if (sdv==0)
		return;

	if (unsigned r=(pk[0]-a);r<48*(1+(sdv>>3))){
		std::sort(a,pk[0]);
	}
	else
		radix(sdv-8,a,pk[0]);
	for (unsigned i=1;i<256;i++){
		if (unsigned r=(pk[i]-pk[i-1]);r<48*(1+(sdv>>3))){
			std::sort(pk[i-1],pk[i]);
		}
		else radix(sdv-8,pk[i-1],pk[i]);
	}

}

void test(unsigned n,bool use_radix=false){
	std::default_random_engine gen(_rdtsc());
	std::uniform_int_distribution<int> ds(-2147483648,2147483647);
	std::vector<int> arr(n);
	for (unsigned i=0;i<n;i++)//заполнение случайными
		arr[i]=ds(gen);

	unsigned t1,t2;

	if (use_radix){
		t1=clock();
		radix(24,arr.data(),arr.data()+arr.size());
		t2=clock();
		printf("radix sort %d in %.3f ms\n",n,1.0e3*double(t2-t1)/CLOCKS_PER_SEC);
	}else{
		t1=clock();
		std::sort(arr.begin(),arr.end());
		t2=clock();
		printf("std sort %d in %.3f ms\n",n,1.0e3*double(t2-t1)/CLOCKS_PER_SEC);
	}


}

int main()
{
	test(100000);
	test(1000000);
	test(10000000);
	test(100000,true);
	test(1000000,true);
	test(10000000,true);
}