public class MergeSort {
public static void main(String[] args) {
int[] a={1,3,5,6,7};
int[] b={2,4,8,9,10};
getResult(a,b);
}
//合并两个有序数组
public static int[] mergeArray(int[] a,int[] b){
int a_length=a.length;
int b_length=b.length;
int[] c=new int[a_length+b_length];
int i=0,j=0,k=0; //i 为a数组的元素下标，j为b数组，k为新数组
while(i<a_length&&j<b_length){
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
}
//哪个数组还有元素未添加，则添加进c数组即可
while(i<a_length) c[k++]=a[i++];
while(j<b_length) c[k++]=b[j++];
return c;
}
//非有序数组，先拆分到只剩下一个元素 再进行有序合并
public static int[] mergeSort(int[] a,int start,int end){
if(start<end){
int mid=(start+end)/2; //分区
int left[]=mergeSort(a,start,mid);
int right[]=mergeSort(a,mid+1,end);
return mergeArray(left,right);
}else{//当只有一个元素时，直接返回
int left[]=new int[1];
left[0]=a[start];
return left;
}
}
public static void getResult(int[] a,int[] b){
int[] left=mergeSort(a,0,a.length-1); //第一个数组通过递归分区排序
int[] right=mergeSort(b,0,b.length-1);//递归分区排序 再合区
int[] result=mergeArray(a,b); // 采用有序数组归并
for(int i=0;i<result.length;i++)
System.out.println(result[i]);
}
}
