归并排序法（Merge Sort，以下简称MS）是分治法思想运用的一个典范。其主要算法操作可以分为以下步骤： Step 1：将n个元素分成两个含n/2元素的子序列 Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列） Step 3：合并两个已排序好的序列 易知，MS的关键在于Merge过程。对于这一过程的理解，算法导论中给出了一个形象的模型。 即假设桌面上有两堆已排序好的的牌，且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌（选取之后，堆顶端又会露出新的顶牌），选取较小的一张，放入输出堆，另一张放回。 重复这一步骤，最后直到一堆牌为空。由于两堆牌都是已排序，所以可知，只要将剩下的那堆牌盖到输出堆即完成整个排序过程。
public int[] mergeSort(int[] A, int n) { // write code here sort(A, 0, n - 1); return A; } public void sort(int[] data, int left, int right) { if (left < right) { int middle = (left + right) / 2; // 划分左右 sort(data, left, middle); sort(data, middle + 1, right); // 合并左右 merge(data, left, middle, right); } } // 合并左右两个子数组 public void merge(int[] data, int left, int middle, int right) { // 临时数组 int[] tempArr = new int[right - left + 1]; // 左边数组游标 int leftIndex = left; // 右边数据游标 int rightIndex = middle + 1; // 临时数组游标 int tempIndex = 0; while (leftIndex <= middle && rightIndex <= right) { // 临时数组选取左、右子数组中小数值 if (data[leftIndex] < data[rightIndex]) { tempArr[tempIndex++] = data[leftIndex++]; } else { tempArr[tempIndex++] = data[rightIndex++]; } } // 剩余的直接放入 while (leftIndex <= middle) { tempArr[tempIndex++] = data[leftIndex++]; } // 剩余的直接放入 while (rightIndex <= right) { tempArr[tempIndex++] = data[rightIndex++]; } // 将临时数组放回原数组相应位置 int temp = 0; while ((temp + left) <= right) { data[left + temp] = tempArr[temp]; temp++; } }归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的
