归并排序的思想：先将数组不断二分，直到不能分时再进行合并。 如：3, 1, 5, 6, 4, 2, 5 先分成3，1，5，6和4，2，5 再对3，1，5，6和4，2，5再进行二分，以3，1，5，6举例： 3，1，5，6被分成3，1和5，6，对3，1再进行二分，得到3和1。因为3和1都不能再进行二分，故而对3，1进行合并，得到1，3。同理5，6合并得到5，6。再对1，3和5，6进行合并得到1，3，5，6。最后将1，3，5，6和合并得到的2，4，5（以同样的思维得到）再进行合并得到1，2，3，4，5，5，6。 具体代码实现如下：
package com.wsy.sort; public class MergeSort { /** * 归并排序 * * @param a * @param left * @param right */ public static void mergeSort(int[] a, int left, int right) { int middle = (left + right) / 2; if (left < right) { mergeSort(a, left, middle); mergeSort(a, middle + 1, right); merge(a, left, middle, right); } } /** * 合并2个已经排好序的数组 * * @param a * @param left * @param middle * @param right */ private static void merge(int[] a, int left, int middle, int right) { int i = left; int j = middle + 1; int k = 0; int[] tmp = new int[right - left + 1]; while (i <= middle && j <= right) { if (a[i] < a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i <= middle) { tmp[k++] = a[i++]; } while (j <= right) { tmp[k++] = a[j++]; } // 给a数组赋值,注意是从a数组的第left个开始 for (int m = 0; m < tmp.length; m++) { a[m + left] = tmp[m]; } } public static void main(String[] args) { int[] a = new int[] { 3, 1, 5, 6, 4, 2, 5 }; mergeSort(a, 0, 6); for (int i = 0; i < a.length; i++) { System.out.println(" " + a[i]); } } }