归并排序，同样是利用分治思想的典型算法例子，下面简单总结下归并排序。

一、归并的概念

　　归并是这样一种概念，它针对两个或者多个有序的数组，是合并这多个有序数组并进行排序的一种手段，它的主要处理方法是每次都找出比较各个数组的首个元素（假设从左边开始排序而且是升序的方式），找出他们之间的最小值，将其拷贝到一个新的数组上，依次类推直到所有元素处理完，看说明图：

归并很好地利用了两个数组均是有序的这个条件，合并两个数组，大概只需要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的常数倍，所以它比较消耗内存空间。

本文转自 sshpp 51CTO博客，原文链接：http://blog.51cto.com/12902932/1926576，如需转载请自行联系原作者