public class MergeSort {

    //归并排序两个有序链表
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    //归并排序两个有序数组
    private static int[] mergeTwoArray(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int l = 0, r = 0;
        for (int index = 0; index < result.length; index++) {
            if (l >= left.length)
                result[index] = right[r++];
            else if (r >= right.length)
                result[index] = left[l++];
            else if (left[l] > right[r])
                result[index] = right[r++];
            else
                result[index] = left[l++];
        }
        return result;
    }

    private static int[] mergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return mergeTwoArray(mergeSort(left), mergeSort(right));
    }

}