import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.*;

class Solution {
    Random random = new Random(System.currentTimeMillis());

    void popul(int[] ar) {
        for (int i = 0; i < ar.length; i++) {
            ar[i] = random.nextInt();
        }
    }

    interface ProcessIntArray {
        void process(int[] arr);
    }

    public Future<Double> measure(int[] arr, ProcessIntArray processIntArray, ExecutorService es) {
        Callable<Double> task = () -> {
            long start = System.nanoTime();
            processIntArray.process(arr);
            long end = System.nanoTime();
            return (end - start) / 1000000000.0;
        };
        return es.submit(task);
    }


    public void start() throws ExecutionException, InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(8);

        int size = 1000 * 1000;
        int[] quickSortArray = new int[size];
        popul(quickSortArray);
        int[] bubbleSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
        int[] mergeSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
        int[] originalArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
        int[] insertionSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);

        Future<Double> bubbleSortTime = measure(bubbleSortArray, Solution::bubbleSort, executorService);
        Future<Double> insertionSortTime = measure(insertionSortArray, Solution::insertionSort, executorService);
        Future<Double> quickSortTime = measure(quickSortArray, Solution::quickSort, executorService);
        Future<Double> mergeSortTime = measure(mergeSortArray, Solution::mergeSort, executorService);


        System.out.println();
        System.out.println("array size:     " + size);
        System.out.println("quick sort:     " + quickSortTime.get() + "s");
        System.out.println("merge sort:     " + mergeSortTime.get() + "s");
        System.out.println("insertion sort: " + insertionSortTime.get() + "s");
        System.out.println("bubble sort:    " + bubbleSortTime.get() + "s");
        executorService.shutdown();

        for (int i = 0; i < quickSortArray.length; i++) {
            if (quickSortArray[i] != bubbleSortArray[i] || quickSortArray[i] != mergeSortArray[i] || quickSortArray[i] != insertionSortArray[i]) {
                throw new RuntimeException(Arrays.toString(originalArray));
            }
        }
    }


    public static void mergeSort(int[] ar) {
        if (ar.length < 5) {
            bubbleSort(ar);
            return;
        }
        int pivot = ar.length / 2;
        int[] ar2 = new int[pivot];
        int[] ar3 = new int[ar.length - pivot];
        for (int i = 0; i < ar.length; i++) {
            if (i < pivot) {
                ar2[i] = ar[i];
            } else {
                ar3[i - pivot] = ar[i];
            }
        }
        mergeSort(ar2);
        mergeSort(ar3);
        int ar2idx = 0;
        int ar3idx = 0;
        int arIndexCounter = 0;
        while (true) {
            int whatToPutInAR = 0;
            if (ar2idx != ar2.length && ar3idx != ar3.length) {
                if (ar2[ar2idx] < ar3[ar3idx]) {
                    whatToPutInAR = ar2[ar2idx];
                    ar2idx++;
                } else {
                    whatToPutInAR = ar3[ar3idx];
                    ar3idx++;
                }
            } else if (ar2idx != ar2.length) {
                whatToPutInAR = ar2[ar2idx];
                ar2idx++;
            } else if (ar3idx != ar3.length) {
                whatToPutInAR = ar3[ar3idx];
                ar3idx++;
            } else if (arIndexCounter != ar.length) {
                throw new RuntimeException("wtf");
            }
            if (arIndexCounter == ar.length) return;
            ar[arIndexCounter++] = whatToPutInAR;
        }
    }

    private static void quickSort(int[] ar) {
        quickSort(ar, 0, ar.length);
    }

    static public void quickSort(int[] array, int start, int end) {
        boolean changed = false;
        if (end == 0) return;
        int pivot = array[end - 1];
        int partitionCandidate = start;
        for (int i = start; i < end; i++) {
            if (array[i] < pivot) {
                swap(array, partitionCandidate++, i);
                changed = true;
            } else if (pivot < array[i]) {
                swap(array, end - 1, i);
                changed = true;
            }
        }
        if (start < partitionCandidate) {
            quickSort(array, start, partitionCandidate);
        }
        if (partitionCandidate < end) {
            if (partitionCandidate != start || changed) quickSort(array, partitionCandidate, end);
        }
    }


    public static void swap(int[] ar, int from, int to) {
        int old = ar[from];
        ar[from] = ar[to];
        ar[to] = old;
    }

    public static void bubbleSort(int[] ar) {
        for (int i = 0; i < ar.length; i++) {
            for (int j = 0; j < ar.length - 1; j++) {
                if (ar[j] > ar[j + 1]) {
                    swap(ar, j + 1, j);
                }
            }
        }
    }

    private static void insertionSort(int[] ar) {
        for (int i = 0; i < ar.length; i++) {
            for (int j = i; j >= 1; j--) {
                boolean breaker = true;
                if (ar[j] < ar[j - 1]) {
                    breaker = false;
                    swap(ar, j - 1, j);
                }
                if (breaker) break;
            }
        }
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {
    	System.out.println(System.getProperty("java.version"));
        Solution s = new Solution();
        while (true) s.start();
    }
}