import java.util.Random;

public class Sort {

    public static void main(String[] args) {
        System.out.println("Quick sort time testing");
        int[] a = generateRandomArray(20000000);
        quickSort(a);
        long time = System.currentTimeMillis();
        System.out.println("Second quick sort");
        quickSort(a);
        System.out.println("Time: " + (System.currentTimeMillis() - time));

        // Quick sort time testing
        // 804249086
        // Second quick sort
        // 689381057
        // Time: 669
        //
        // Much much fast with the pivot, first test, the second sort just didnt finish

        // System.out.println("Merge 20k");
        // int[] a = generateRandomArray(20000000);
        // long time = System.currentTimeMillis();
        // mergeSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // System.out.println("Merge 40k");
        // a = generateRandomArray(40000000);
        // time = System.currentTimeMillis();
        // mergeSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // System.out.println("Merge 80k");
        // a = generateRandomArray(80000000);
        // time = System.currentTimeMillis();
        // mergeSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // System.out.println("Quick 20k");
        // a = generateRandomArray(20000000);
        // time = System.currentTimeMillis();
        // quickSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // System.out.println("Quick 40k");
        // a = generateRandomArray(40000000);
        // time = System.currentTimeMillis();
        // quickSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // System.out.println("Quick 80k");
        // a = generateRandomArray(80000000);
        // time = System.currentTimeMillis();
        // quickSort(a);
        // System.out.println(
        // "Time: " + (System.currentTimeMillis() - time));

        // Merge 20k
        // 1665416280
        // Time: 2650
        // Merge 40k
        // 3470823619
        // Time: 5415
        // Merge 80k
        // 7221650896
        // Time: 11359
        // Quick 20k
        // 948351822
        // Time: 1838
        // Quick 40k
        // 2017226144
        // Time: 3788
        // Quick 80k
        // 4163682230
        // Time: 7875
        // Seems like quick is much faster
    }

    private static Random rand = new Random();

    static long comparisons;

    public static void quickSort(int[] a) {
        comparisons = 0;
        quickSort(a, 0, a.length - 1);
        System.out.println(comparisons);
    }

    private static void quickSort(int[] a, int start, int end) {
        if (start < end) {
            int pivot = partition(a, start, end);
            quickSort(a, start, pivot - 1);
            quickSort(a, pivot + 1, end);
        }
    }

    private static int partition(int[] a, int start, int end) {
        int mid = (start + end) / 2;

        int pivotIndex;
        if (
            (a[start] <= a[mid] && a[mid] <= a[end]) ||
            (a[end] <= a[mid] && a[mid] <= a[start])
        ) {
            pivotIndex = mid;
        } else if (
            (a[mid] <= a[start] && a[start] <= a[end]) ||
            (a[end] <= a[start] && a[start] <= a[mid])
        ) {
            pivotIndex = start;
        } else {
            pivotIndex = end;
        }
        swap(a, pivotIndex, end);

        int pivot = start - 1;
        for (int i = start; i <= end; i++) {
            comparisons++;
            if (a[i] <= a[end]) {
                comparisons++;
                swap(a, ++pivot, i);
            }
        }
        return pivot;
    }

    public static void mergeSort(int[] a) {
        comparisons = 0;
        mergeSort(a, 0, a.length - 1);
        System.out.println(comparisons);
    }

    private static void mergeSort(int[] a, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);
            mergeSort(a, mid + 1, end);
            merge(a, start, mid, end);
        }
    }

    public static void merge(int[] a, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int left = start;
        int right = mid + 1;
        int i = 0;
        while (left <= mid && right <= end) {
            comparisons += 2;

            if (a[left] < a[right]) {
                comparisons++;
                temp[i++] = a[left++];
            } else {
                temp[i++] = a[right++];
            }
        }
        while (left <= mid) {
            comparisons++;
            temp[i++] = a[left++];
        }

        while (right <= end) {
            comparisons++;
            temp[i++] = a[right++];
        }
        for (i = 0; i < temp.length; i++) {
            comparisons++;
            a[start++] = temp[i];
        }
    }

    public static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    public static int[] generateRandomArray(int length) {
        int[] a = new int[length];
        for (int i = 0; i < length; i++) a[i] = rand.nextInt(length * 10);
        return a;
    }

    public static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) return false;
        return true;
    }
}