package com.company;

public class Main {
    public static int[] Merge(int[] left, int[] right) {
        int[] answer = new int[left.length + right.length];
        int i1 = 0;
        int i2 = 0;
        for (int i = 0; i < answer.length; i++) {
            if (i2 == right.length||(i1 < left.length && left[i1] < right[i2])) {
                answer[i] = left[i1];
                i1++;
            } else {
                answer[i] = right[i2];
                i2++;
            }
        }
        return answer;
    }

    public static int[] mergeSort(int[] toSort) {
        if (toSort.length > 1){
            int[] left = new int[(toSort.length / 2) + toSort.length % 2];
            int[] right = new int[toSort.length / 2];
            int j = 0;
            for (int i = 0; i < left.length; i++) {
                left[i] = toSort[j];
                j++;
            }
            for (int i = 0; i < right.length; i++) {
                right[i] = toSort[j];
                j++;
            }
            toSort = Merge(mergeSort(left), mergeSort(right));
        }
        return toSort;
    }

    public static void main(String[] args) {
        int[] a = new int[]{4234,715,7,885,532,55896523,5468793,57881,4355778,66,3523,35794524,6586743};
       a = mergeSort(a);
    }

}