SortRandomNumber

class LapTimeInfo {
    private String tag;
    private long lapTime;

    public LapTimeInfo(String tag, long lapTime) {
        this.tag = tag;
        this.lapTime = lapTime;
    }

    public void printOut() {
        System.out.format("%s: %d ms\n", tag, lapTime);
    }
}


import java.util.*;

class SortRandomNumber {

    final static int INPUT_COUNT = 1000000;
    static long checkpointMilliTime;
    static List<LapTimeInfo> lapTimeList = new ArrayList<LapTimeInfo>();

    public static void main(String args[]) {

        checkpointMilliTime = System.currentTimeMillis();

        /*
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int[] a = new int[num];
        int[] b = new int[num];

        for (int i = 0; i < num; i++) {
            a[i] = input.nextInt();
        }
        */
        int[] inputNumbers = new int[INPUT_COUNT];
        int[] outputNumbers = new int[INPUT_COUNT];
        for(int i=0; i<INPUT_COUNT; i++) {
            inputNumbers[i] = (int)(Math.random() * INPUT_COUNT);
        }

        markLapTime("Input numbers");

        countingSort(inputNumbers, outputNumbers, INPUT_COUNT);
        markLapTime("Counting Sort");

        printOutput(INPUT_COUNT, outputNumbers);
        markLapTime("Print Output");

        for(LapTimeInfo lapTimeInfo :  lapTimeList) {
            lapTimeInfo.printOut();
        }
    }

    private static void markLapTime(String tag) {
        lapTimeList.add(new LapTimeInfo(tag, System.currentTimeMillis() - checkpointMilliTime));
        checkpointMilliTime = System.currentTimeMillis();
    }

    private static void printOutput(int num, int[] b) {
        for (int i = 0; i < num; i++) {
            System.out.println(b[i]);
        }
    }

    public static void countingSort(int a[], int b[], int num) {
        int k = 2000001;
        int c[] = new int[k];
        for (int i = 0; i < k; i++) {
            c[i] = 0;
        }
        for (int j = 0; j < num; j++) {
            c[a[j] + k / 2]++;
        }
        for (int i = 1; i < k; i++) {
            c[i] = c[i] + c[i - 1];
        }
        for (int j = num - 1; j >= 0; j--) {
            b[c[a[j] + k / 2] - 1] = a[j];
            c[a[j] + k / 2]--;
        }
    }

}