class Solution {
    public static void mergeSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int[] helper = new int[nums.length];
        mergeSort(nums, helper, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    private static void mergeSort(int[] nums, int[] helper, int low, int high) {
        if (low < high) {
            int middle = low + (high - low) / 2;
            mergeSort(nums, helper, low, middle);
            mergeSort(nums, helper, middle + 1, high);
            merge(nums, helper, low, middle, high);
        }
    }

    private static void merge(int[] nums, int[] helper, int low, int middle, int high) {
        for (int i = low; i <= high; i++) {
            helper[i] = nums[i];
        }

        int left = low;
        int right = middle + 1;
        int curr = low;
        while (left <= middle && right <= high) {
            if (helper[left] <= helper[right]) {
                nums[curr++] = helper[left++];
            } else {
                nums[curr++] = helper[right++];
            }
        }

        int remain = middle - left;
        for (int i = 0; i <= remain; i++) {
            nums[curr + i] = helper[left + i];
        }
    }
}