// Karve, Patel, and Reynolds

void rsort(int*A, int*B, int n);

void sort(int* A, int n)
{
    int B[n];
    int i, j = n, k = 0, numNegKeys, v;
    int mask = 8388608;
    
    
    for(i = 0; i < n; i++){
	
	v = A[i];
	
	if(v & mask)
	    B[k++] = v;
	else
	    B[--j] = v;
    }
    numNegKeys = k;
    mask = 4194304; // = 2^22; isolates bit 23
    k = 0;
    
    //parition the bin of negative keys by the next bi
    for(i = 0; i < numNegKeys; i++){
	v = B[i];
	
	if(v & mask)
	    A[--j] = v;
	else
	    A[k++] = v;
    }
    rsort(A, B, k);
    rsort(&A[k], B, numNegKeys-k); 
    
    j = n;
    k = numNegKeys;
    //partition the positive keys by the next bit
    for(; i < n; i++){
	v = B[i];
	
	if(v & mask)
	    A[--j] = v;
	else
	    A[k++] = v;
    }
rsort(&A[numNegKeys], B, k-numNegKeys);
rsort(&A[k], B, n-j);

}

void rsort(int * A, int*B, int n)
{
	struct bitField
	{
		unsigned : 10;
		unsigned rad2 : 11;
		unsigned rad1 : 11;
	};

    int i = n-1;
    int j;
    int k;
    //int p;
    
    //int B[n];
    int rad1Hist[4096];
    int * rad2Hist = &(rad1Hist[2048]);
    struct bitField *m;
    //int *s = &A[n-1];
    unsigned long *p = (unsigned long *)rad1Hist;

	int *r1, *r2, *r1_1, *r2_2, *sp;


	for (k=0; k<4096; k++)	// ??? faster than p>rad1Hist because easier to unroll
	{
		*p=0;
		p++;
	}

	m = (struct bitField *) &A[n-1];

	
	for (i=n-1; i>=0; i--)		// is it faster to run for loop so you compiler can unroll it easily.
	{

		//rad1Hist[(unsigned short) (*s)]++;	// this has one less assignment but maybe internal multiplication
		r1 = rad1Hist + m->rad1;
		++(*r1);
		r2 = rad2Hist + m->rad2;
		++(*r2);
		m--;
	}
	
	r1=rad1Hist;
	r2=rad2Hist;//ch  all for loops and offset loops
	(*r2)--;
	r2_2 = r2;
	r2++;
	(*r1)--;
	r1_1 = r1;
	r1++;
	for(j=1; j<2048; j++)
	{
		*r1 += *r1_1;
		r1_1 = r1;
		r1++;	// will this do r1 = r1 + 1*sizeof whatever type r1 is pointing to
		// if so  then we will be better of by doing r1 = r1 + 4 saving 1 multiplication;
		*r2 += *r2_2;
		r2_2 = r2;
		r2++;
		
}
	//printf ("Finished rad1.\n");

	sp=&A[n-1];	// make s point to end of A;
	//s++;
	
	for (i=n-1; i>=0; i--)//while (sp >= A)//
	{
		r1 = rad1Hist + ((struct bitField*)(sp))->rad1;
		B[*r1] = *sp;
		(*r1)--;
		//x--;
		//s -= 4;
		sp--;
	}

	//printf ("Finished pass for rad1.\n");

	//s=(unsigned short *)&B[n-1];
	sp = &B[n-1];

	for (i=n-1; i>=0; i--)//while (sp >= B)
	{
		r2 = rad2Hist + ((struct bitField*)(sp))->rad2;
		A[*r2] = *sp;
		(*r2)--;
		//x--;
		sp--;
	}

	//printf ("Finished pass of rad2.\n");	
	
}