public class MergeSort {
    public static int[] merge(int[] array) {
        if(array.length == 1)
            return array;

        int lengthHalf = array.length / 2;
        int[] leftArray = new int[lengthHalf];
        int[] rightArray = new int[array.length - lengthHalf];

        for(int j = 0; j < rightArray.length; j++) {
            rightArray[j] = array[j + leftArray.length];
        }

        leftArray = merge(leftArray);
        rightArray = merge(rightArray);

        int leftIndex = 0;
        int rightIndex = 0;

        for(int k = 0; k < array.length; k++) {
            if(rightIndex >= rightArray.length || (leftIndex < leftArray.length && leftArray[leftIndex] < rightArray[rightIndex])) {
                array[k] = leftArray[leftIndex];
                leftIndex++;
            } else {
                array[k] = rightArray[rightIndex];
                rightIndex++;
            }
        }

        return array;
    }
}