package MerSort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

import static java.lang.System.in;
import static java.lang.System.out;

/**
 * Created by NgT on 5/11/2016.
 */
public class MergeSort {
    public static void checkInput(int n) {
        int[] array;

        Scanner scanner = new Scanner(in);
        while (true) {
            try {
                out.println("Enter the number of array: ");
                n = Integer.parseInt(scanner.nextLine());
                array = new int[n];
                if (n <= 0) {
                    throw new Exception();
                }
                break;
            } catch (Exception e) {
                out.println("Wrong input. Try again!");
            }
        }
        sorting(array, n);
    }

    public static void sorting(int[] array, int n) {
        int i;
        Random random = new Random();
        array = new int[n];
        out.println("Unsorted array: ");
        for (i = 0; i < n; i++) {
            array[i] = random.nextInt(n);
        }
        out.println(Arrays.toString(array));
        out.println("Sorted array: ");
        mergeSort(array, 0, n - 1);
        out.println(Arrays.toString(array));
    }

   public static void mergeSort(int[] a, int low, int high) {
        int N = high - low;
        if (N <= 1)
            return;
        int mid = low + N / 2;
        // recursively sort
        mergeSort(a, low, mid );
        mergeSort(a, mid , high);
        merge(a, low, mid , high);
    }
    public static void merge(int[] a, int low, int mid, int high){
        int N = high - low;
        int[] temp = new int[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++) {
            if (i == mid)
                temp[k] = a[j++];
            else if (j == high)
                temp[k] = a[i++];
            else if (a[j] < a[i])
                temp[k] = a[j++];
            else
                temp[k] = a[i++];
        }
        for (int k = 0; k < N; k++)
            a[low + k] = temp[k];
    }




    public static void main(String[] args) {
        int n = 0;
        checkInput(n);
    }
}