Radix sort

Kod do sortowania unsigned intów w czasie liniowym. ( O(n) )
O wiele lepszy od jakiegokolwiek algorytmu dzialajacego w czasie liniowo-logarytmicznym ( O(n lg n)), jak np. quicksort.

Algorytm jest stabilny, nie działa w miejscu (uzywa bufora tymczasowego o rozmiarze n).

#include <stdio.h>


//Radix Sort by Fr3m3n, 2007
#define uint unsigned int

typedef union _sort_uint{
	uint liczba;
	struct{
		#ifdef LITTLE_ENDIAN
			unsigned short int Low;
			unsigned short int High;
		#else
			unsigned short int High;
			unsigned short int Low;
		#endif
	};
}sort_uint;

int main(void){
	uint n;
	scanf("%u",&n);
	sort_uint *liczby0=(uint*)malloc(n*sizeof(uint)*2);
	//liczby1 to tablica pomocnicza
	sort_uint *liczby1=liczby0+n;
	for(uint i=0;i<n;i++)
		scanf("%u",&liczby0[i].liczba);
	/*
	Najpierw sortuje wedlug lsw (least significant word), uzywajac lsw jako indexu w tablicy.
	Pozniej w ten sam sposob z msw. (most significant word)
	Zlozonosc obliczeniowa: O(n)
	Zlozonosc pamieciowa: O(n)
	Sortuje wg unsigned int, ale latwo zmienic dla signed
	*/
	uint gdzie[0xFFFF+1];
	bzero(gdzie,sizeof(gdzie));
	for(register uint i=0;i<n;i++)
		gdzie[liczby0[i].Low]++;
	register uint t=0,t1;
	//zapisz w gdzie adresy dla kolejnych liczb
	for(uint i=0;i<(0xFFFF+1);i++){
		if(gdzie[i]){
			t1=gdzie[i];
			gdzie[i]=t;
			t+=t1;
		}
	}
	//posortuj wg lsw
	for(register uint i=0;i<n;i++){
		register uint __asdf=(liczby0[i].Low);
		liczby1[gdzie[__asdf]].liczba=liczby0[i].liczba;
		gdzie[__asdf]++;
	}

	//posortuj wg msw
	bzero(gdzie,sizeof(gdzie));
	for(register uint i=0;i<n;i++)
		gdzie[liczby1[i].High]++;
	t=0;
	//zapisz w gdzie adresy dla kolejnych liczb
	for(uint i=0;i<(0xFFFF+1);i++){
		if(gdzie[i]){
			t1=gdzie[i];
			gdzie[i]=t;
			t+=t1;
		}
	}
	//posortuj wg msw
		for(register uint i=0;i<n;i++){
			register uint __asdf=(liczby1[i].High);
			liczby0[gdzie[__asdf]].liczba=liczby1[i].liczba;
			gdzie[__asdf]++;
	}

	//wypisz
	puts("Posortowane:");
	for(uint i=0;i<n;++i)
		printf("%u\n",liczby0[i].liczba);
	free(liczby0);
}