1.算法思想：

　　基于分治法。将待排序序列分成两个长度相等的子序列，为每个子序列排序，然后将它们合并成一个序列。——两路归并

2.代码实现：

static void merge(int[] arr1,int[] arr2,int left,int mid,int right{//合并两个子序列，即待排序序列arr1以mid为界的左右两个子序列各自有序，将二者合成一个有序序列

　　for(int i=left;i<=right;i++)

　　{

　　　　arr2[i]=arr1[i];//arr2用来存放待排序序列初始的元素

　　}

　　int s1=left,s2=mid+1,t=left;

　　while(s1<=mid&&s2<=right){

　　　　if(arr2[s1]<=arr2[s2])

　　　　　　arr1[t++]=arr2[s1++];

　　　　else

　　　　　　arr1[t++]=arr2[s2++];

　　}

　　while(s1<=mid){

　　　　arr1[t++]=arr2[s1++];

　　}

　　while(s2<=left){

　　　　arr1[t++]=arr2[s2++];

　　}

}

static void mergeSort(int[] a1,int[] a2,int left,int right){

　　if(left>=right) return;//如果当前排序序列长度为1，则返回

　　int mid=(left+right)/2;

　　mergeSort(a1,a2,left,mid);//分别对以mid为分界的左右两个子序列进行归并排序

　　mergeSort(a1,a2,mid+1,right);

　　merge(a1,a2,left,mid,right);//将排好序的两个子序列合并

}

3.性能分析：

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：稳定