import java.util.*;
/* Implementation of (counting based) radix sort for 32-bit integers.
 *
 * To run performance test: java -Xms32m -Xmx256m RadixSorting
 * @author Rasmus Pagh 2009
 */

class GoodRadixSorting {

    public static void radixSort(int[] A){
	// Radixsort for 32 bit integers, using 2 passes
	// Uses counting to simplify memory allocation
	// Precondition: Array has only positive integers

	int n=A.length;
	int[] countL = new int[65536]; // Low character counts
	int[] countH = new int[65536]; // High character counts
        int[] tmp = new int[n]; // Temporary for result of first pass

	// Count character occurrences, low and high bits:
	for (int i=0; i<n; i++) { 
	    countL[A[i]&65535]++;
	    countH[A[i]>>16]++;
	}

	// Compute prefix sums ("memory allocation"):
	for (int i=1; i<65536; i++) { 
	    countL[i]+=countL[i-1];
	    countH[i]+=countH[i-1];
	}

	// Sort by least significant char. A->tmp
	for (int i=0; i<n; i++) tmp[--countL[A[i]&65535]]=A[i];

	// Sort by most significant char. tmp->A (backwards for stability)
	for (int i=n-1; i>=0; i--) A[--countH[tmp[i]>>16]]=tmp[i];

    }
    
    public static void main(String[] args) {
	for (int r=256; r<=33554432; r=r*2) {
            int[] T=new int[r];

	    Random rand = new Random(System.currentTimeMillis());

            for (int i=0; i<r; i++) T[i]=rand.nextInt(1073741824);

	    long startTime = System.currentTimeMillis();
	    radixSort(T);
	    System.out.println("Sorted "+r+" integers in "+(System.currentTimeMillis()-startTime)+" ms.");
	}

    }    
}


/* From example run, MacBook Pro laptop:

java -Xms600m -Xmx600m GoodRadixSorting
Sorted 256 integers in 3 ms.
Sorted 512 integers in 2 ms.
Sorted 1024 integers in 1 ms.
Sorted 2048 integers in 2 ms.
Sorted 4096 integers in 1 ms.
Sorted 8192 integers in 2 ms.
Sorted 16384 integers in 1 ms.
Sorted 32768 integers in 3 ms.
Sorted 65536 integers in 4 ms.
Sorted 131072 integers in 7 ms.
Sorted 262144 integers in 10 ms.
Sorted 524288 integers in 22 ms.
Sorted 1048576 integers in 49 ms.
Sorted 2097152 integers in 114 ms.
Sorted 4194304 integers in 231 ms.
Sorted 8388608 integers in 470 ms.
Sorted 16777216 integers in 905 ms.
Sorted 33554432 integers in 1881 ms.

*/