一、排序思想

归并排序是采用分治算法，即将一个大问题切分成一些小问题然后递归求解。归并排序的图解如下：

image.png

分的过程简单，就是将数组拆开来，拆到每组只有一个元素为止。治的过程是怎么排序的呢？以最后一次治为例，即将4 5 7 8和1 2 3 6合并成最终的有序序列为例，看看如何实现。

首先创建一个新的数组tempArr，长度为要进行“治”的两个数组长度之和；
然后用i指向4，即第一个数组的最左边，j指向1，即第二个数组的最左边；
发现4比1大，那么就将1存入tempArr，同时指针j后移；
继续比较指针i和j所指元素的大小，发现2比4小，将2存入tempArr，同时j继续后移；
继续比较，将3存入tempArr，j继续后移；
此时发现6比4大，就将4存入tempArr，同时i后移；
5比6小，将5存入tempArr，i继续后移；
7比6大，将6存入tempArr，此时j已经处于最后了，不能后移了；
接着就将i所指的剩余元素都存入tempArr，这个tempArr就是有序的了。

欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。

二、代码实现

1. 第一种方式：

这种方式很容易懂，我们先不是要拆分数组吗？那就拆呗，拆到什么时候为止呢？拆出来的数组只有一个元素了那就不用拆了。

拆分：

public static int[] sort(int[] arr) {
    if (arr == null || arr.length == 1) {
        return arr;
    }
    // 拆分数组
    int mid = arr.length / 2; // 中间指针，利用该指针将数组拆分
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    // 调用合并方法，因为left和right可能可以再拆分，所以传进去的left和right再递归调用当前方法
    return merge(sort(left), sort(right));
}

合并：该方法传入两个数组，对数组进行合并上面已经讲了思路，按照思路来写就好了：

public static int[] merge(int[] left, int[] right) {
    // 定义临时数组
    int[] tempArr = new int[left.length + right.length];
    // 定义两个指针
    int i = 0; // left的指针
    int j = 0; // right的指针
    // 进行合并操作
    for(int index=0; index < tempArr.length; index ++) {
        // 如果left的遍历完了，那么将right中的剩余元素全部依次放入tempArr中
        if (i >= left.length) {
            tempArr[index] = right[j];
            j++; // 指针后移
        } else if(j >= right.length) {
            // 如果right遍历完了，那么将left中剩余的元素全部依次放入tempArr中
            tempArr[index] = left[i];
            i++; // 指针后移
        } else if (left[i] < right[j]) {
            // 如果i所指的数更小，就将该数存入tempArr
            tempArr[index] = left[i];
            i++; // 指针后移
        } else {
            // 如果j所指的数大于等于i所指的数，就将j所指的数存入tempArr
            tempArr[index] = right[j];
            j++; // 指针后移
        }
    }
    return tempArr;
}

没错，这样就搞定了，这就是完全按照上面案例分析来做的，不过缺点就是，拆分的时候，是真正的拆除两个数组来了，会浪费空间，优点就是容易理解。

2. 第二种方式：

第二种方式就是不真正的将数组拆成两部分，而是通过一个中间索引mid，将数组标识成两部分。这样就不需要真正的拆分，不会浪费空间，但是代码相对来说更难理解。

合并：先看合并部分，除了原始数组外，还有三个参数，left和mid构成左边的数组，mid+1和right构成右边的数组，只要理解了这一点，下面的代码就容易理解了。

public static void merge(int[] arr, int left, int mid, int right) {
    // 定义临时数组
    int[] tempArr = new int[right - left + 1]; 
    int i = left; // 左边数组的指针
    int j = mid + 1; // 右边数组的指针
    int k = 0; // 临时数组的指针
    // 当左边数组和右边数组都还没遍历完的时候
    while(i <= mid && j <= right) {
        // 如果i所指的元素更小，就其放入tempArr，同时i后移
        if (arr[i] <= arr[j]) {
            tempArr[k++] = arr[i++];
        } else {
            // 如果j所指的更小，就将其放入tempArr，同时j后移
            tempArr[k++] = arr[j++];
        }
    }
    // 如果左边的数组还没遍历完，就将左边数组剩余元素依次放入tempArr中
    while (i <= mid) {
        tempArr[k++] = arr[i++];
    }
    // 如果右边的数组还没遍历完，就将右边数组剩余元素依次放入tempArr中
    while (j <= right) {
        tempArr[k++] = arr[j++];
    }
    // 将tempArr中排好序的添加到原数组中
    for(int x=0; x<tempArr.length; x++) {
        arr[left + x] = tempArr[x];
    }
}

拆分：拆分到什么时候为止呢，如果left和right相等了，表示只有一个元素，那就不用拆了，否则就对左边和右边的都进行递归拆分，拆到不可再拆就合并。

public static void sort(int[] arr, int left, int right) {
    // 如果左指针和右指针相等，表示只有一个元素，那就不需要拆分了
    if (left == right) {
        return;
    }
    // 否则就进行拆分
    int mid = left + (right - left) / 2; // 找到中间值进行拆分
    // 对左边再进行拆分
    sort(arr, left, mid);
    // 对右边再进行拆分
    sort(arr, mid+1, right);
    // 进行合并
    merge(arr, left, mid, right);
}

经测试，对1000万个随机数进行排序，大概需要2秒，方式一和方式二时间上差不多，但是方式二可以省不少的内存，大家可以在执行的时候看看内存的占用情况。