import java.awt.*;

public class RadexchSort extends ShowSort {
	public static void main(String args[]) {
		RadexchSort applet = new RadexchSort();
		applet.launch("Radix Exchange Sort");
	}

	void doSort() {
		inplace_dir=true;
		inplace_pos=NUM;
		
		int i=0;
		int largest=array[0];

		for (int j=1; j<NUM; j++) {
			if (array[j] > largest)
				largest = array[j];
		}

		for (int n=largest>>1; n != 0; n>>=1)
			i++;
		
		radexchSort(array, 0, NUM-1, i);
		
		inplace_pos = 0;
	}

	int bit(int x, int which) {
		return ((x >> which) & 1);
	}
	

	void radexchSort(int array[], int bottom, int top, int b) {
		if (top > bottom && b >= 0) {
			int lo = bottom, hi = top;
			while (lo != hi) {
				while (bit(array[lo], b)==0 && lo<hi) {
					compared(lo);
					lo++;
				}
				
				while (bit(array[hi], b)!=0 && lo<hi) {
					compared(hi);
					hi--;
				}
				
				
				int temp = array[lo];
				array[lo] = array[hi];
				array[hi] = temp;

				swapped(hi);
			}
			if (bit(array[top], b)==0)
				hi++;

			compared(top);
			
			radexchSort(array, hi, top, b-1);
			inplace_pos=hi;
			radexchSort(array, bottom, hi-1, b-1);
		}
	}	
}