概念

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。

基本思想

归并排序是分治法的典型应用，那么分治法是什么？

分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解。

归并排序中的分，就是将待排序的序列切割，比如原来有8个数，分成4个一组，每个含4个元素的序列有序后，再合并使之成为最终有序的8个元素的序列。但是4个元素的排序依然是“复杂问题”，那么继续分割，直到分割成一个序列只有一个元素时子问题变得“可解”，因为一个元素就是有序序列嘛。

public void mergeSort(int[] a, int low, int high){
        int mid = (low + high)/2;
        if(low < high)//递归出口low=high说明一个序列只有一个元素
        {
            mergeSort(a, low, mid);//使左半序列有序
            mergeSort(a, mid + 1, high);//使右半序列有序
            merge(a, low, mid, high);//合并左右两半序列，使全序列有序
        }
    }

归并排序中的合，就是将已经有序的两个序列合并，使全序列有序。在合并时具体的做法是：
1、左右两个指针，开始时分别指向左右序列的起始位置；
2、比较指针所指向的两个元素，取出较小值放入新数组中；
3、取出数的那个序列指针后移；
4、重复步骤2，直到其中一个序列的数被取完为止；
5、若有序列还有数未被取完，则将这个序列直接接到新数组之后。

public int[] merge(int[] a, int low, int mid, int high){
        int[] temp = new int[high - low + 1];
        int l = low;
        int m = mid + 1;
        int k = 0;
        while (l <= mid && m <= high){
            if(a[l] <= a[m]){
                temp[k++] = a[l++];
            }else{
                temp[k++] = a[m++];
            }
        }
        while (l <= mid){
            temp[k++] = a[l++];
        }
        while (m <= high){
            temp[k++] = a[m++];
        }
        for(int i = 0; i < temp.length; i++){
            a[i + low] = temp[i];
        }
        return a;
    }

最后贴一个归并排序的递归过程图帮助理解。