一、排序思想
归并排序是采用分治算法，即将一个大问题切分成一些小问题然后递归求解。归并排序的图解如下：
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秒，方式一和方式二时间上差不多，但是方式二可以省不少的内存，大家可以在执行的时候看看内存的占用情况。
