归并排序

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]);
    
}

}