归并排序将一个数组分成两半，对着两半分别排序，在将它们归并为一个有序数组，通常是以递归的形式表达的。
假设两个数组各自有序，归并两个有序数组很简单，但需要添加一个临时数组，用来从头到尾处理这两个数组。将一个数组中的元素与另一个数组中的元素相比较，并将较小的元素复制到临时数组中去，其过程如下：
第一个数组 第二个数组 临时数组
1 3 6 0 2 4
1>0，故将0放入临时数组 0
1<2, 故将1放入临时数组 1
3>2, 故将2放入临时数组 2
3<4, 故将4放入临时数组 3
6>4, 故将4放入临时数组 4
将第一个数组剩余部分复制到临时数组 6
在归并排序中，待归并的两个有序数组实际上是原数组的两半。也就是谁将原数组分为两半，对这两把分别排序，将排序后的这两半归并为第二个临时数组，然后将这个临时数组复制回原数组。过程如下
原数组 3 1 6 2 4 0
分为两半 3 1 6 2 4 0
对两半分别排序 1 3 6 0 2 4
归并 （过程见上） 0 1 2 3 4 6
分半采用递归的形式
整个的代码实现如下:
package mergeSort;
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int []nums,int left,int right){
int mid=(left+right)/2;
if(left<right) {
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums,left,mid,right);
}
}
public static void merge(int nums[],int left,int mid,int right){
int []temp=new int[right-left+1];//临时数组
int rightFirst=mid+1;//右边数组第一个元素
int leftFirst=left;//左边数组第一个元素
int tempIndex=0;//临时数组的索引
while(leftFirst<=mid&&rightFirst<=right){
if(nums[leftFirst]<nums[rightFirst]){
temp[tempIndex++]=nums[leftFirst++];
}else{
temp[tempIndex++]=nums[rightFirst++];
}
}
while(leftFirst<=mid){
temp[tempIndex++]=nums[leftFirst++];
}
while(rightFirst<=right){
temp[tempIndex++]=nums[rightFirst++];
}
for(int i=0;i<temp.length;i++){
nums[i+left]=temp[i];
}
}
public static void main(String[] args) {
int []nums={2,3,1,8,5,1,11,2,45,5,67,3,0};
mergeSort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}
}
原文：http://www.cnblogs.com/pokid/p/4925505.html