归并排序算法

归并排序采用分治法（Divide and Conquer），是一种稳定的排序方法。顾名思义，其实就是通过先递归、再合并的思想来排序。

 

如下图所示，假设有一个无序数组{10, 4, 6, 3, 8, 2, 5, 7}，

先根据二分法对其进行递归分解，

第一次分解后，变成两个数组{10, 4, 6, 3}, {8, 2, 5, 7}，

第二次分解后，变成四个数组{10, 4}, {6, 3}, {8, 2}, {5, 7}，

直到分解成一个数组只包含一个元素，

 

然后再对元素进行比较、合并，

第一次合并后，变成四个数组{4, 10}, {3, 6}, {2, 8}, {5, 7}

第二次合并后，变成两个数组{3, 4, 6, 10}, {2, 5, 7, 8}

直到合并成一个有序的数组。

 

Java示例代码：

import java.util.Arrays;

public class MergeSort {
 public static void main(String[] args) {
  Integer[] a = { 10, 4, 6, 3, 8, 2, 5, 7 };
  mergeSort(a);
  System.out.println(Arrays.toString(a));
 }

 @SuppressWarnings("rawtypes")
 public static void mergeSort(Comparable[] a) {
  Comparable[] tmp = new Comparable[a.length];
  mergeSort(a, tmp, 0, a.length - 1);
 }

 @SuppressWarnings("rawtypes")
 private static void mergeSort(Comparable[] a, Comparable[] tmp, int left,
   int right) {
  if (left < right) {
   int center = (left + right) / 2;
   mergeSort(a, tmp, left, center);
   mergeSort(a, tmp, center + 1, right);
   merge(a, tmp, left, center + 1, right);
  }
 }

 @SuppressWarnings({ "rawtypes", "unchecked" })
 private static void merge(Comparable[] a, Comparable[] tmp, int left,
   int right, int rightEnd) {
  int leftEnd = right - 1;
  int k = left;
  int num = rightEnd - left + 1;

  while (left <= leftEnd && right <= rightEnd)
   if (a[left].compareTo(a[right]) <= 0)
    tmp[k++] = a[left++];
   else
    tmp[k++] = a[right++];

  while (left <= leftEnd)
   // Copy rest of first half
   tmp[k++] = a[left++];

  while (right <= rightEnd)
   // Copy rest of right half
   tmp[k++] = a[right++];

  // Copy tmp back
  for (int i = 0; i < num; i++, rightEnd--)
   a[rightEnd] = tmp[rightEnd];
 }
}