分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。 归并排序算法基本流程：
分解待排序的n个元素的序列成各具n/2个元素的两个子序列；使用归并排序递归地排序两个子序列；合并两个已排序的子序列以产生已排序的答案。Java代码实现：
class Mergesort { public static void main(String[] args) { int[] arr = {5, 2, 4, 6, 1, 3}; merge_sort(arr, 0, arr.length - 1); for (int a : arr) { System.out.print(a + ","); } } // 归并排序 private static void merge_sort(int[] arr, int i, int j) { if (i < j) { int q = (i + j) / 2; // 分成左右两部分，递归调用排序算法 merge_sort(arr, i, q); merge_sort(arr, q + 1, j); merge(arr, i, q, j); } } // 排序两个已排序的序列 private static void merge(int[] arr, int i, int q, int j) { int[] left = new int[q - i + 1]; System.arraycopy(arr, i, left, 0, left.length); int[] right = new int[j - q]; System.arraycopy(arr, q + 1, right, 0, right.length); int m = 0, n = 0, k = i; while (m < left.length && n < right.length) {// 左右两个数组比较，将小的复制到arr[]中 if (left[m] <= right[n]) { arr[k] = left[m]; m++; } else { arr[k] = right[n]; n++; } k++; } if (m == left.length) {// 左边被复制完 for (int x = n; x < right.length; x++) { arr[k] = right[x]; k++; } } else {// 右边被复制完 for (int y = m; y < left.length; y++) { arr[k] = left[y]; k++; } } } }归并排序的时间复杂度为O(nlgn)。
