题目：对于一个int数组，请编写一个归并排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：[1,2,3,5,2,3],6[1,2,2,3,3,5]
示例参考Array11：数组中的逆序对。归并排序使用了“分治”的思想，采用递归来实现。首先写一个divide(array,left,right)方法用来分割数组，
this.divide(array,tempArray,start,middle);
this.divide(array,tempArray,middle+1,end);
this.merge(array,tempArray,start,end);
这是一个递归的方法，递归的边界条件是当分割后的两侧数组只有一个元素时停止分割，在divide()里面在求出middle并且递归调用divlde(array,start,middle)和divide(array,middle+1,end)的下面是合并方法merge(array,start,end,tempArray)方法，merge不是一个递归的方法，只是用来将array数组中从start到end之间的部分数组进行排序，已知此时start~middle和middle+1~end都是已经排好序的，因此在对这两个子数组进行合并时使用2个指针从start和middle+1开始遍历数组，选择较大值放入到临时数组中即可，对两个子数组遍历合并完成后，将临时数组tempArray中从start到end部分的值覆盖到array数组中，之后tempArray就可以覆盖写入，因此整个程序的空间复杂度是O(n)而不用是O(n^2).
for(inti=start;i<=end;i++){
array[i]=tempArray[i];
}
即归并排序时需要单独实现两个方法divide(),merge()，然后在主函数中只需要调用divide即可。
this.divide(array,tempArray,0,array.length-1);
归并排序时间复杂度O(nlogn)，空间复杂度O(n)
import java.util.*;
//归并排序：先分割再合并，分割方法里面有合并方法
public class MergeSort {
public int[]mergeSort(int[] A, int n) {
//特殊输入
if(A==null||A.length<=0) return A;
//调用divide()对整个数组(从0到length-1)进行分割合并
this.divide(A,0,A.length-1);
return A;
}
//写一个divide()递归方法用来对数组进行分割并将分割后的部分排序
public voiddivide(int[] array,int start,int end){
//求出待分割数组的中点
intmiddle=(start+end)/2;
//递归一定要有终止的边界条件，本题中的边界条件是要分割的数组只有1个元素
if(start==end)return;
//继续对左右子数组进行分割，假设执行this.divide()方法后数组就分成了两个部分了
this.divide(array,start,middle);
this.divide(array,middle+1,end);
//此时[start,end]已经被分成了2个子数组且2个子数组都已经排好序了，直接将其合并即可
this.merge(array,start,end);
}
//写一个merge(start,end)方法将里面的两个已经排序的子数组进行排序,合并两个排序的子数组需要使用辅助数组
public voidmerge(int[] array,int start,int end){
//创建辅助数组，合并子数组时需要用到这个辅助数组，每次合并之后将结果覆盖到array中[start,end]部分，之后辅助数组就可以覆盖重用了
int[]tempArray=new int[array.length];
//得到数组的中间点
int middle=(start+end)/2;
//已知[start,middle],[middle+1,end]是已经排好序的
//设置2个指针遍历2个数组，找出最小值，放入到辅助数组中
int p1=start;
int p2=middle+1;
//设置指针p指向辅助数组的当前元素
int p=start;
//注意此时是对[start,end]范围内的子数组进行排序合并，因此排序后的元素在辅助数组中的范围也是[start,end]
while(p1<=middle&&p2<=end){
if(array[p1]<=array[p2]){
tempArray[p++]=array[p1++];
}else{
tempArray[p++]=array[p2++];
}
}
//如果p1越界表示数组1已经遍历完成，于是只需要将数组2中的剩余元素直接复制到辅助数组中即可
if(p1>middle){
while(p2<=end){
tempArray[p++]=array[p2++];
}
}
//如果p2越界便是数组2已经遍历完成，于是只需要将数组1中的剩余元素直接复制到辅助数组中即可
if(p2>end){
while(p1<=middle){
tempArray[p++]=array[p1++];
}
}
//此时合并完后的结果存放在辅助数组tempArray[start,end]中，要将其覆盖到array数组
for(inti=start;i<=end;i++){
array[i]=tempArray[i];
}
}
}