归并排序的优点不说了。
做归并排序之前，我先试着将两个有序数组进行排序，合并成一个有序数组。
思路：定义好两个有序数组，理解的时候我先思考了数组只有一个数组的排序，然后是两个元素的数组的排序，思路就有了，先比较两个数组的首元素，谁更小就放入结果数组里面，然后指针下移，继续比较，直到有一个数组为空，停止比较，因为是有序数组，那么不为空的数组后面的元素都比之前存入结果数组的要大，且是有序的，因此，只需将后面的数组存入结果数组即可。
接下来是代码实现：
/*
? ? * 分治算法利用
? ? * 两个有序数组的合并
? ? * 将有序数组i,数组j,合并成c
? ? */
? ? public Integer[] sort(Integer[] i, Integer[] j, Integer[] c){
? ? ? ? c = new Integer[i.length+j.length];
? ? ? ? int i1 = 0;? //i的数组指针
? ? ? ? int j1 = 0; //j的数组指针
? ? ? ? int c1 = 0; //c的数组指针
? ? ? ? while(i1 < i.length&&j1 < j.length){
? ? ? ? ? ? if(i[i1] > j[j1]){
? ? ? ? ? ? ? ? c[c1++] = j[j1];
? ? ? ? ? ? ? ? j[j1++] = null;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? c[c1++] = i[i1];
? ? ? ? ? ? ? ? i[i1++] = null;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? /*
? ? ? ? * i之后还有元素
? ? ? ? */
? ? ? ? while(i1
? ? ? ? ? ? c[c1++] = i[i1];
? ? ? ? ? ? i[i1++] = null;
? ? ? ? }
? ? ? ? /*
? ? ? ? * j之后还有元素
? ? ? ? */
? ? ? ? while(j1 < j.length){
? ? ? ? ? ? c[c1++] = j[j1];
? ? ? ? ? ? j[j1++] = null;
? ? ? ? }
? ? ? ? return c;
? ? }
以上实现了将两个有序数组的合并，而归并排序，那么将一条无序数组分组成任意多个有序数组即可，并不需要确认是否是有序数组，一个数组里一个元素肯定是有序的，那么我要做的只是，递归实现数组分解，然后将有两个序数组合并。
将一个数组分解，可以用分治的方法，定义头，尾，和中间指针，然后下次的递归，只需变换中间指针即可。
而排序最开始只需要比较头部的一个元素和尾部的一个元素；
依次向上递归。
算了，贴代码吧。
public int[] mergeSort(int[] num,int first,int last){
? ? ? ? int mid = (first+last)/2;
? ? ? ? if(first < last){
? ? ? ? ? ? mergeSort(num,first,mid);
? ? ? ? ? ? mergeSort(num,mid+1,last);
? ? ? ? ? ? merge(num,first,mid,last);
? ? ? ? }
? ? ? ? return num;
? ? }
? ?
? ? public void merge(int[] num,int first,int mid,int last){
? ? ? ? int _left = first; //左指针
? ? ? ? int _right = mid+1; //右指针
? ? ? ? int[] temp = new int[last - first + 1];
? ? ? ? int temp_p = 0;
? ? ? ? while(_left<=mid&&_right<=last){
? ? ? ? ? ? if(num[_left]
? ? ? ? ? ? ? ? temp[temp_p++] = num[_left++];
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? temp[temp_p++] = num[_right++];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? while(_left<=mid){
? ? ? ? ? ? temp[temp_p++] = num[_left++];
? ? ? ? }
? ? ? ? while(_right<=last){
? ? ? ? ? ? temp[temp_p++] = num[_right++];
? ? ? ? }
? ? ? ? _left = 0;
? ? ? ? //因为没有返回数组，所以排序好的数组应该放在num数组里面，直接覆盖即可，注意下标。
? ? ? ? for(int i : temp){
? ? ? ? ? ? num[(_left++)+first] = i;
? ? ? ? }
? ? }
first，last为数组头尾指针。