算法 - 归并排序

给定一个无序数组，使用归并排序法对数组进行从小到大排序。

原理： 将数组一分为二，二分为四，直到不可切分，然后排序、合并。（先分后治）

@Test
public void testMergeSort() {
    int[] arr = {4, 2, 1, 5, 7, 6, 3};
    mergeSort(arr, 0, arr.length - 1);
    // -- output :  [1, 2, 3, 4, 5, 6, 7]
    System.out.println(Arrays.toString(arr));
}

private void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        //中心点
        int mid = low + (high - low) / 2;
        //左区间排序
        mergeSort(arr, low, mid);
        //右区间排序
        mergeSort(arr, mid + 1, high);
        //合并左右区间排序结果
        merge(arr, low, mid, high);
    }
}

private void merge(int[] arr, int low, int mid, int high) {
    //左区间起点，终点为mid
    int i = low;
    //右区间起点，终点为high
    int j = mid + 1;
    //临时数组，用来存储排序结果,大小为: high - low + 1
    int[] temp = new int[high - low + 1];
    int t = 0;

    //归并
    while (i <= mid || j <= high) {
        //当左右区间都未排完序
        if (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        //当左区间还有未排序序的
        else if (i <= mid) {
            temp[t++] = arr[i++];
        }
        //当右区间还有未排序序的
        else {
            temp[t++] = arr[j++];
        }
    }

    //将排序结果赋值给原数组
    for (int e : temp) {
        arr[low++] = e;
    }
}