// Banfield

#define SIZE 1000000

void radix_sort_neg(int x[],int neg_counter)
{
	int *y,bits,count,i,counter,begin_array;
	y=(int*)malloc(neg_counter*sizeof(int));
	for(bits=0;bits<24;bits++)
	{
		counter=0;
		begin_array=0;
		for(count=0;count<neg_counter;count++)
		{
			if (((x[count] >> bits) & 1) != 1)
			{
				counter=counter+1;
            }
        }
		for(count=0;count<neg_counter;count++)
		{
			if (((x[count] >> bits) & 1) != 1)
			{
				y[begin_array]=x[count];
				begin_array=begin_array+1;
			}
			else
			{
				y[counter]=x[count];
				counter=counter+1;
			}
		}
		for(count=0;count<neg_counter;count++)
			x[count]=y[count];	
	}
}

void radix_sort_pos(int x[], int pos_counter)
{
	int *y,bits,count,counter,begin_array;
	y=(int*)malloc(pos_counter*sizeof(int));
	for(bits=0;bits<24;bits++)
	{
		counter=0;
		begin_array=0;
		for(count=0;count<pos_counter;count++)
		{
			if (((x[count] >> bits) & 1) != 1)
			{
				counter=counter+1;
            }
        }
		for(count=0;count<pos_counter;count++)
		{
			if (((x[count] >> bits) & 1) != 1)
			{
				y[begin_array]=x[count];
				begin_array=begin_array+1;
			}
			else
			{
				y[counter]=x[count];
				counter=counter+1;
			}
		}
		for(count=0;count<pos_counter;count++)
			x[count]=y[count];	
	}
}

void sort(int* x, int n)
{
	int *neg,*pos,counter,neg_counter=0,pos_counter=0, i;
	int pos_counter2=0,neg_counter2=0;
    
	for (counter=0;counter<SIZE;counter++)
		if (x[counter]<0)
			neg_counter=neg_counter+1;
		else
			pos_counter=pos_counter+1;
	neg=(int*)malloc(neg_counter * sizeof(int));
	pos=(int*)malloc(pos_counter * sizeof(int));
    for (counter=0;counter<SIZE;counter++)
		if (x[counter]<0)
		{
			neg[neg_counter2]=x[counter];
			neg_counter2=neg_counter2+1;
		}
		else
		{
			pos[pos_counter2]=x[counter];
			pos_counter2=pos_counter2+1;
		}
	radix_sort_neg(neg,neg_counter);
	radix_sort_pos(pos,pos_counter);
	for(counter=0;counter<neg_counter;counter++)
		x[counter]=neg[counter];
    for(counter=neg_counter;counter<SIZE;counter++)
	    x[counter]=pos[counter-neg_counter];
}