概念
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（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;
}
最后贴一个归并排序的递归过程图帮助理解。
