将一个需要排序的数组先把它从中间一分为而，然后在对每个子数组递归排序，然后将两个排序好的数组合二为一
//归并排序的时间复杂度是O（nlogn）
public static void mergeSort(int [] a){
if(a.length>1){//递归的退出条件
//将原来的数组分为b,c
int [] b = new int[a.length/2];
int [] c = new int[a.length-b.length];
int index = 0;
for (int i = 0;i<a.length;i++){
if(i<b.length)
b[i] = a[i];
else
c[index++] = a[i];
}
//递归的将子数组b,c排序
mergeSort(b);
mergeSort(c);
//将排序好的b,c合并到a数组
merge(b,c,a);
}
}
//合并两个数组到原数组，数组b,c是a的子数组
public static void merge(int [] b,int [] c,int [] a){
int i = 0;//b数组的下标
int j = 0;//c数组的下标
int k = 0;//a数组的下标
int p = b.length;
int q = c.length;
while(i<p&&j<q){//次循环的目的是将b数组和c数组中小的值放入a数组，直到一个数组中的元素全部放入a数组中
if(b[i]<=c[j]){
a[k++] = b[i++];
}else{
a[k++] = c[j++];
}
}
//将b或c数组中剩余的元素放入数组a当中
if(i==p){
for(;j<q;j++){
a[k++] = c[j];
}
}else{
for(;i<p;i++){
a[k++] = b[i];
}
}
}
