归并排序，同样是利用分治思想的典型算法例子，下面简单总结下归并排序。
一、归并的概念
归并是这样一种概念，它针对两个或者多个有序的数组，是合并这多个有序数组并进行排序的一种手段，它的主要处理方法是每次都找出比较各个数组的首个元素（假设从左边开始排序而且是升序的方式），找出他们之间的最小值，将其拷贝到一个新的数组上，依次类推直到所有元素处理完，看说明图：
归并很好地利用了两个数组均是有序的这个条件，合并两个数组，大概只需要2n次比较即可（n是较小数组的长度），下面贴上归并的算法代码:
//归并方法
public static void mergeAB(int [] arrA,int [] arrB,int [] arrC){
//循环遍历两个需要归并的数组
for(int a=0,b=0,c=0;c<(arrA.length+arrB.length);){
//判断两个数组是否对应遍历完成
if(a==arrA.length){
//遍历完成A数组，则对应B中的元素只需要直接复制到C数组中
arrC[c++] = arrB[b++];
continue;
}
if(b==arrB.length){
arrC[c++] = arrA[a++];
continue;
}
//如果两个数组都没有遍历完，则进行比较操作
arrC[c++] = arrA[a]<arrB[b]?arrA[a++]:arrB[b++];
}
}
二、归并排序
归并排序是利用分治的思想进行递归归并的过程，递归过程不断对数组进行拆分，直到可以直接归并为止（可以认为是要处理的元素只有两个元素的时候，也可以认为是一个元素的时候）。其实理解了分治思想，归并排序理解起来还是挺简单的，下面简单贴上算法：
//归并排序方法
public static int [] guiBingSort(int [] arr,int l,int r){
//确定递归停止条件
if(l==r){
return new int[]{arr[r]};
}
//分两部分进行递归操作
int [] result1 = guiBingSort(arr, l, l+(r-l)/2);
int [] result2 = guiBingSort(arr, l+(r-l)/2+1, r);
//result1和result是已经排好序的数组，进行归并操作即可
int [] rtn = new int[result1.length + result2.length];
mergeAB(result1, result2, rtn);//调用归并方法
//返回归并结果
return rtn;
}
三、归并排序的特征
归并排序大概有一下特征：
1、它是稳定的排序算法，不改变元素之间的相对位置；
2、归并排序的比较次数和元素的初始顺序无关，而且都是nlogn次；
3、归并排序需要的内存空间是N的常数倍，所以它比较消耗内存空间。
本文转自帅气的头头博客51CTO博客，原文链接http://blog.51cto.com/12902932/1926576如需转载请自行联系原作者
sshpp
