下面先看一个归并排序过程的示例： 待排序列（14,12,15,13,11,16）： 首先用分割的方法，将这个序列分割成一个个已经排好序的子序列，然后再利用归并的办法将一个个子序列合并成排好序的序列，如下图：
上面很明显就是采用先 “分割” 再 “合并” 的思想。我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
下面首先考虑怎么把两个有序的序列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。源码如下：
/** * 把有序数组a和有序数组b 合并到数组c中，这里假设数组c的容量足够大，可以容纳数组a和数组b中的所有元素。 * @param a * @param n 数组a的长度n * @param b * @param m 数组b的长度m * @param c */ public static void mergeArray(int a[], int n, int b[], int m, int c[]){ int i,j,k; //索引 i=j=k=0; while (i < n && j < m){ if(a[i] < b[j]){ c[k++] = a[i++]; } else { c[k++] = b[j++]; } } //将数组a或则b中剩余的元素加入数组c中 while (i<n){ c[k++] = a[i++]; } while (j < m){ c[k++] = b[j++]; } }//end上面的合并算法的效率还是比较高的，可以达到O(n)的时间复杂度。
上面已经解决了合并有序序列的问题，下面再来看看二路归并的方法，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后 再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 源码如下：
/** * 将a[first, mid] 和 a[mid+1, last] 合并 * @param a * @param first * @param mid * @param last * @param temp */ private static void mergeArray(int a[], int first, int mid, int last, int temp[]){ int i = first, j=mid+1;//设置两个数组的起始边界 int m=mid, n=last;//设置两个数组的结束边界 int k=0; while (i <= m && j<=n){ if(a[i] <= a[j]){ temp[k++] = a[i++]; }else { temp[k++] = a[j++]; } } while (i<=m){ temp[k++] = a[i++]; } while (j <= n){ temp[k++] = a[j++]; } for(i=0; i<k; i++){ a[first+i] = temp[i]; } } /** * 二路归并 使用递归解决. * @param a * @param first 数组的起始下标 * @param last 数组的结束下标 * @param temp 辅助数组 */ public static void mergeSort(int[] a, int first, int last, int[] temp){ if(first < last) { int mid = (first + last)/2; mergeSort(a, first, mid, temp);//左边有序 mergeSort(a, mid+1, last, temp);//右边有序 mergeArray(a, first, mid, last, temp); //再将两个有序序列合并. } }测试：
public static void main(String[] args) { int[] arr = {1,9,3,12,7,8,3,4,65,22}; int[] temp = {0,0,0,0,0,0,0,0,0,0}; mergeSort(arr, 0, arr.length-1, temp); for(int i:arr){ System.out.print(i+","); } }输出：
1,3,3,4,7,8,9,12,22,65,归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
