并归排序的过程就是一个先拆再合并的过程，先拆到全是不能再拆的最小数组，然后组与组之间合并，排序的过程在合并的过程中执行。
所以整个算法分两部分，split和merge
先说merge吧，将两个数组合并为新数组，符合从大到小。
public int[] merge(int[] c1, int[] c2) {
int[] ret = new int[c1.length + c2.length];
for (int i = 0, j = 0, index = 0; i < c1.length || j < c2.length; ) {
if (i < c1.length) {
if (j < c2.length) {
if (c1[i] >= c2[j]) {
ret[index++] = c2[j++];
} else {
ret[index++] = c1[i++];
}
} else {
ret[index++] = c1[i++];
}
} else {
ret[index++] = c2[j++];
}
}
return ret;
}
邓老师的教案给出过另外一种复杂校验的版本，不过其教案上也注明了，从效率的角度而言，还是这样拆开来写比较好。。。
merge方法的条件是两个已经排好序的数组c1和c2，返回值则是也已经排好序的包括c1和c2所有内容的另一数组。
其中是有一个for循环来着，逻辑上可以用IntStream.iterate来代替，但代码中对c1，c2，ret的操作都是寻秩访问，IntStream.iterate的执行过程大多是对指针的操作而非数据本身，就很麻烦。。不知道咋写。
split方法需要执行的操作是将数组分到不能再分。
不过这边不需要返回执行结果，只需要对于每个拆分出来的两个对象继续进行split操作，当不能进行split了，则merge。
spilit的实现如下：
public void split(int[] ins, int a, int b) {//3 6
int mid = (a + b) / 2;
if (b - a <= 2) {
//无非两种情况
if (b - 1 > a && ins[a] > ins[b - 1]) {
int temp = ins[a];
ins[a] = ins[b - 1];
ins[b - 1] = temp;
}
return;
}
split(ins, a, mid);
split(ins, mid, b);
merge(ins, a, mid, mid, b);
}
split传入的参数就是待排序数组ins，排序区间[a,b)本身是个递归算法，所有操作直接在ins上执行就好了，所以是不需要返回值的（返回值也没啥意义）。
其逻辑就是拆分拆分拆分和mergemergemerge。不过需要个if去判断一下待排序区间的大小，如果区间只有两个元素，判断一下然后进行一下交换就行了。至于为毛要有这个一个if，因为if语句后面的语句依然执行的是split，其中依然需要传入排序区间[a,b)，上文也提到了
之后需要对merge方法进行一些改造，大致就是，原来的merge是由两个int数组创建一个新的int数组，而新的merge方法，最好是接近原地算法，在原数组上直接进行修改，那用数组，跟排序区间，即可表示原来的一个数组。
public void merge(int[] ori, int c1_left, int c1_right, int c2_left, int c2_right) {
int[] temp = new int[c1_right - c1_left];
System.arraycopy(ori, c1_left, temp, 0, temp.length);
int c1_length = c1_right - c1_left;
for (int i = 0, j = c2_left, index = c1_left; i < c1_length || j < c2_right; ) {
if (i < c1_length) {
if (j < c2_right) {
//都合法
if (temp[i] >= ori[j]) {
ori[index++] = ori[j++];
} else {
ori[index++] = temp[i++];
}
} else {
ori[index++] = temp[i++];
}
} else {
ori[index++] = ori[j++];
}
}
}
不过似乎无论是在split还是在merge当中，由于其大量的寻秩操作，其对秩和位置进行操作，而不是对数组中的值进行操作，流以及函数式编程，在这种算法中的应用范围不广，并不适合。