归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。要想理解归并算法，我们先来看看对两个有序的数组如何进行升序（即由小到大）排序：
设两个数组为a和b，很自然地，我们能想到用两个数组的第一个元素即a[0]和b[0]进行比较，将较小地结果放入结果数组，这里假设a[0]<b[0]，那么a[0]放入结果数组，由于a[1]>a[0],而b[0]>a[0],a[1]和b[0]大小无法确定，所以我们接着比较a[1]和b[0],...以此类推，谁小就放入结果数组，并用下一个元素进行比较，直到某个数组所有元素放入结果数组，然后只需要把另一数组剩下的元素依次放入结果数组中，代码如下所示：
//对有序数组a[]和b[]进行排序 private int[] mergeArray(int a[], int b[]) { int[] result = new int[a.length + b.length]; //分别代表a,b,result数组的下标指示器 int i = 0; int j = 0; int k = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) result[k++] = a[i++]; else result[k++] = b[j++]; } //判定a数组是否有剩余，如果有将a数组剩余元素放入结果数组 while (i < a.length) result[k++] = a[i++]; //判定b数组是否有剩余，如果有将b数组剩余元素放入结果数组 while (j < b.length) result[k++] = b[j++]; return result; } 我们可以看到，对有序数组的排序的时间复杂度为O（n），效率非常好。那我们是否可以利用这个操作对数组进行排序呢？如果可以的话，那么核心问题就是如何得到有序数组？聪明如你，我想你已经猜到了，我们可以把待排序数组拆分为A、B两个数组（两路归并），然后对AB数组进行同样地拆分，直到拆分出来的数组只含有一个元素，一个元素的数组自然可以看作是有序了，那么，很自然，我们将这些单个元素的数组两两按照上面类似地做法进行排序，最终就可以得到一个排序好的数组，这也是归并算法的核心思想，实现代码如下：
import java.util.Arrays; /* *两路归并算法实现 */ public class MergeSort { /** * 对数组array中start到end之间元素进行排序 * @param array 待排序数组 * @param start 排序起始索引 * @param end 排序截止索引 * @return 输出有序数组 */ public static int[] sort(int[] array, int start, int end) { int mid = (start + end) / 2; if (start < end) { // 左边有序 sort(array, start, mid); // 右边有序 sort(array, mid + 1, end); // 左右归并 merge(array, start, mid, end); } return array; } public static void merge(int[] array, int start, int middle, int end) { //用于存储中间结果 int[] temp = new int[end - start + 1]; //分别代表a,b,temp临时数组的下标指示器 int i = start; int j = middle + 1; int k = 0; // 把较小的数先移到中间结果数组中 while (i <= middle && j <= end) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } //判定a数组是否有剩余，如果有将a数组剩余元素放入结果数组 while (i <= middle) { temp[k++] = array[i++]; } //判定b数组是否有剩余，如果有将b数组剩余元素放入结果数组 while (j <= end) { temp[k++] = array[j++]; } // 将中间结果写入到最终结果中 for (int l = 0; l < temp.length; l++) { array[l + start] = temp[l]; } } } 好的，我们针对int型数组的归并排序算法就大功告成了！那么，接下来，我们要如何让我们的这个算法能对任意类型的数组进行排序呢？
