合并两个有序的链表和这题很像，但是合并两个有序的链表可以使用递归来实现，因为链表的结点有next域，数组没有。
但是我们可以看到，合并两个有序的数组合并后的数组也是有序的，这会让我们把思路放到排序算法上。合并两个有序的数组的过程是和归并排序的merge过程很类似
贴一下归并排序的代码 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr==null) return null;
        sort(arr,0,arr.length-1);
        return arr;
    }
    public void merge(int[] arr,int left,int mid,int right){
        int[] help=new int[right-left+1];
        int p1=left,p2=mid+1,i=0;
        while(p1<=mid&&p2<=right){
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        while(p2<=right){
            help[i++]=arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[left+i]=help[i];
        }
    }
    public void sort(int[] arr,int left,int right){
            if(left==right) return;
            int mid=left+(right-left)/2;
            sort(arr,left,mid);
            sort(arr,mid+1,right);
            merge(arr,left,mid,right);
    }
}
我们只需要把merge修改一下就好了，代码如下：
 
import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int[] help=new int[m+n];
        int p1=0,p2=0,i=0;
        while(p1<m&&p2<n){
            help[i++]=A[p1]<B[p2]?A[p1++]:B[p2++];
        }
        while(p1<m){
            help[i++]=A[p1++];
        }
        while(p2<n){
            help[i++]=B[p2++];
        }
        i=0;
        for(int c:help){
            A[i++]=c;
        }
    }
}