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

public class MergeSort {

    public static void main(String[] args) {

        Random random = new Random();
        int max = 10000;
        int arr[] = new int[max];

        for (int i=0; i < max; i++) {
            arr[i] = random.nextInt(2147483647);
        }

        System.out.println("boop!");
        long start = System.currentTimeMillis();
        arr = merge(arr).clone();
        long end = System.currentTimeMillis();

        System.out.println("it took " + (end - start) + " milliseconds");
        System.out.println(Arrays.toString(arr));


    }

    public static int[] merge(int[] array) {

        int maxIndex = array.length;
        int halfIndex = (array.length) / 2;


        // if the array was split into one
        if (array.length <= 1) {
            return array;
        }

        int[] subArray1;
        int[] subArray2;
        int[] sorted;

        subArray1 = Arrays.copyOfRange(array, 0, halfIndex);
        subArray2 = Arrays.copyOfRange(array, halfIndex, maxIndex);

        subArray1 = merge(subArray1);
        subArray2 = merge(subArray2);


        sorted = new int[subArray1.length + subArray2.length];


        int index1 = 0, index2 = 0;
        for (int i = 0; i < sorted.length; i++) {

            // if subArray1 ran out of elements
            if (index1 == subArray1.length) {
                for (; i < sorted.length; i++) {
                    sorted[i] = subArray2[index2++];
                }

                break;
            }

            // if subArray2 ran out of elements
            if (index2 == subArray2.length) {
                for(; i < sorted.length; i++) {
                    sorted[i] = subArray1[index1++];
                }

                break;
            }

            if (subArray1[index1] <= subArray2[index2]) {
                sorted[i] = subArray1[index1++];
                continue;
            }


            if (subArray1[index1] > subArray2[index2]) {
                sorted[i] = subArray2[index2++];
                continue;
            }

        }
        return sorted;


    }