// Trifonov, Bromberg

/* Radix sort: 2 pass, 12 bit radix                          */
/* sorts +/- integers differing in the lower 23 bits         */
/* the 24th bit is used for sign determination, allowing a   */
/* range of about +/-8 million for the elements being sorted */
/*                                                           */
/* Borislav Trifonov and Aaron Bromberg, April 2001          */

#include <malloc.h>

void sort(int *a, int n)
{
	register int *i, *j, negatives = 0;
	int *b = (int *)malloc(n * sizeof(int)), *count = (int *)malloc(4097 * sizeof(int));

	for (i = count, j = count + 4097; i < j; i++) *i = 0;
	count++;
	for (i = a, j = a + n; i < j; i++) (*(count + (*i & 4095)))++;
	count--;
	for (i = count + 1, j = count + 4096; i < j; i++) *i += *(i - 1);
	for (i = a, j = a + n; i < j; i++) *(b + ((*(count + (*i & 4095)))++)) = *i;
	for (i = count, j = count + 4097; i < j; i++) *i = 0;
	count++;
	for (i = b, j = b + n; i < j; i++) (*(count + (((*i) >> 12) & 4095)))++;
	for (i = count + 2048, j = count + 4096; i < j; i++) negatives += *i;
	count--;
	*count = negatives;
	for (i = count + 1, j = count + 2048; i < j; i++) *i += *(i - 1);
	*(count + 2048) = 0;
	for (i = count + 2049, j = count + 4096; i < j; i++) *i += *(i - 1);
	for (i = b, j = b + n; i < j; i++) *(a + ((*(count + ((*i >> 12) & 4095)))++)) = *i;

	free(b);
	free(count);
}