class RadixExchangeSort extends SortAlgorithm {
	int bits(int x, int k, int j) 
		{ return (x >> k) & ~(~0 << j); }
	
	void radixexchange(int a[], int l, int r, int b) {
		int i, j; 
		if (r > l && b >= 0) {
			i = l; j = r;
			while (j != i) {
				while (bits(a[i],b,1) == 0 && i < j) i++;
				while (bits(a[j],b,1) == 1 && j > i) j--;
				swap(a,i,j);
				pause();
			}
			if (bits(a[r],b,1) == 0) j++;
			radixexchange(a, l, j-1, b-1);
			radixexchange(a, j, r, b-1);
			pause();
		}
	}
	
    void sort(int a[]) {
    	radixexchange(a, 0, a.length-1, 30);
	}
}