原理：

归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法，该算法采用分治法。将以有序的子序列合并，得到一个完全有序的序列，即：先使得每个子序列有序，再使得子序列段间有序。如果将两个有序表合成一个有序表，称为：二路归并。

我们采用二路归并如图演示：

分解的过程，我们可以借助递归，不停的往下分解，直到只有一个元素分解完成。
合并的过程，就是我们合并两个有序的数组，我们主要是比较两个元素，小的先放，然后放较大的元素。

分解：

java">public static void mergeSort(long[] array) {
        mergeSortRange(array, 0, array.length);
    }

    private static void mergeSortRange(long[] array, int from, int to) {
        if (to - from <= 1) {
            return;
        }
        int mid = (to + from) / 2;
        mergeSortRange(array, from, mid);
        mergeSortRange(array, mid, to);
        
        //合并
        merge(array, from, mid, to);
    }

合并：

java">private static void merge(long[] array, int from, int mid, int to) {
        int size = to - from;
        long[] array2 = new long[size];

        int k1 = from;
        int k2 = mid;
        int k3 = 0;

        while (k1 < mid && k2 < to) {
            if (array[k1] <= array[k2]) {
                array2[k3++] = array[k1++];
            } else {
                array2[k3++] = array[k2++];
            }
        }
        while (k1 < mid) {
            array2[k3++] = array[k1++];
        }
        while (k2 < to) {
            array2[k3++] = array[k2++];
        }
        for (int i = 0; i < size; i++) {
            array[from + i] = array2[i];
        }
    }

非递归：

java">    public static void mergeSort(long[] array) {
        for (int i = 1; i < array.length; i = i * 2) {
            for (int j = 0; j < array.length; j = j + 2 * i) {
                int low = j;
                int mid = j + i;
                if (mid >= array.length) {
                    continue;
                }
                int high = mid + i;
                if (high > array.length) {
                    high = array.length;
                }
                merge(array, low, mid, high);
            }
        }
    }