归并排序：递归+合并。是经典算法——分治法的典型应用。

思路：1）将一串数据，首先分成两部分，每个部分分别排序，然后合并成一串数据。2）在1）中，由于每个部分的数据并不是有序的，两个分串就需要再次分别分成两部分，这样的话就有了4个分串。3）一直往下分，直到分到每个部分只有一个数据，而一个数据必定是有序的，因为只有它自己本身。4）在1）~3）的过程中需要用到递归的思想。分到最低层时进行合并，每个分串的数据不断累加，直到变成2个大串，最后合并成一个整串。

至于有序序列的合并，可以参考。

下面用java代码实现。

/**     * 将两个有序数列进行合并,从小到大     * 有序数列分别为：array[firstIndex...middIndex]     *                   array[middIndex+1...lastIndex]     * @param array 需要重新整合的数组     * @param firstIndex 数组中序列1的起始下标     * @param middIndex 数组中序列1的结束坐标     * @param lastIndex 数组中序列2的结束坐标     * @param tempArray 操作过程中临时用于存放数据的数组     */    private static void mergeArray(int[] array,int firstIndex,                    int middIndex,int lastIndex,                    int[] tempArray) {                //tempArray的坐标        int tempIndex = 0;        //序列1的坐标        int aIndex = firstIndex;        //序列2的坐标        int bIndex = middIndex + 1;                //一旦发现序列1或者2中的其中一个的下标已经到了结束坐标        //需要退出循环，否则会造成内存溢出        while((aIndex <= middIndex) && (bIndex <= lastIndex)) {            if(array[aIndex]

 

/**     * 归并排序：递归 && 合并     *      * 首先，只有一个元素的序列必定是有序的     * 我们可以从一个元素的序列入手，组建成2个元素的有序序列     * 直到最后组建成N个元素的有序序列     * 当然，给定了一个N元素的数组后，就是对上面所述的逆过程     *      * @param array 要排序的数组     * @param firstIndex 数组头     * @param lastIndex 数组尾     * @param tempArray 临时数组     */    private static void mergeSort(int[] array, int firstIndex,                    int lastIndex, int[] tempArray) {        if(firstIndex < lastIndex) {            int middIndex = (firstIndex + lastIndex) / 2;            //左边有序            mergeSort(array, firstIndex, middIndex, tempArray);            //右边有序            mergeSort(array, middIndex + 1, lastIndex, tempArray);            //将两个有序数列合并            mergeArray(array, firstIndex, middIndex, lastIndex, tempArray);        }            }

 

public static void main(String[] args) {        // TODO Auto-generated method stub        int[] tempArray = new int[10];        int[] array = {50,10,90,30,70,40,80,60,20};        mergeSort(array,0,8,tempArray);        for(int i = 0;i <9; i++) {            System.out.println(array[i]);        }    }

 参考文章：