原理
拆分：将数组分成2个子数组，然后对子数组继续进行拆分，直到只有单个元素为止
合并：将2个子数组中的元素依次比较放到辅助数组中，比较完成后，这2个子数组就排序好了，再将辅助数组中的元素覆盖原数组中这2个子数组索引处的元素即可

合并的原理图

示例

package wxw.mengyuan;

/**
 * 归并排序
 */
public class MergeSorting {

  // 辅助数组
  private static Comparable[] assit = null;

  /**
   * 对数组中的元素进行排序
   *
   * @param arr 要排序的数组
   */
  public static void sort(Comparable[] arr) {
    // 初始化辅助数组，与真实数组一样的长度
    assit = new Comparable[arr.length];

    // 调用重载方法进行排序
    sort(arr, 0, arr.length - 1);
  }

  /**
   * 对数组中的索引start-end的元素进行分组排序
   *
   * 原理
   * (1) 求开始索引、结束索引的中间索引
   * (2) 将数组中 [开始索引, 中间索引] 的数据作为一个群组A，内部进行再次分组
   * (3) 将数组中 [中间索引+1, 结束索引] 的数据作为一个群组B，内部进行再次分组
   *
   * @param arr 要排序的数组
   * @param start 开始索引
   * @param end 结束索引
   */
  private static void sort(Comparable[] arr, int start, int end) {
    // 当开始索引与结束索引相遇时，则结束排序
    if (end <= start) {
      return;
    }
    // 堆代码 duidaima.com
    // 求中间索引
    int mid = (start + end) / 2;

    // 分组排序
    // [开始索引, 中间索引] 的数据作为一个群组A，内部进行再次分组排序
    // [中间索引+1, 结束索引] 的数据作为一个群组B，内部进行再次分组排序
    sort(arr, start, mid);
    sort(arr, mid+1, end);

    // 将两个群组A、B进行合并排序
    merge(arr, start, mid, end);
  }

  /**
   * 合并两个群组的数据，并排序
   *
   * 原理
   * (1) 将数组中 [开始索引, 中间索引] 的数据作为一个群组A，这个群组内部是已排序好了的
   * (2) 将数组中 [中间索引+1, 结束索引] 的数据作为一个群组B，这个群组内部是已排序好了的
   * (3) 在辅助数组上指定一个索引指针i，默认指向开始索引
   * (4) 在群组A上指定一个索引指针p1，默认指向开始索引
   * (5) 在群组B上指定一个索引指针p2，默认指向 中间索引+1
   * (6) 比较群组A、B当前索引指针对应的值
   *     (A) 若群组A数据大于群组B数据，则将群组B数据放入辅助数组的索引指针i对应的数据处，群组A当前索引指针+1、辅助数组的索引指针i+1
   *     (B) 若群组B数据大于群组A数据，则将群组A数据放入辅助数组的索引指针i对应的数据处，群组B当前索引指针+1、辅助数组的索引指针i+1
   * (7) 当群组A 或 群组B中没有数据了，则将另一个群组数据全部填入辅助数组的索引指针i及其后面的数据处
   * (8) 将辅助数组中 [开始索引, 结束索引] 的数据拷贝回原数组
   *
   * @param arr 要排序的数组
   * @param start 开始索引
   * @param mid 中间索引
   * @param end 结束索引
   */
  private static void merge(Comparable[] arr, int start, int mid, int end) {
    // 定义3个指针
    // 辅助表的索引指针，从开始索引开始
    int i = start;
    // 第一个群组的索引指针，从开始索引开始
    int p1 = start;
    // 第二个群组的索引指针，从 中间索引+1 开始
    int p2 = mid + 1;

    // 若群组A、B都还有数据，则比较各自当前索引指针对应的值
    while (p1 <= mid && p2 <= end) {
      if (greater(arr[p1], arr[p2])) {
        // 群组A数据大于群组B数据
        assit[i++] = arr[p2++];
      } else {
        // 群组B数据大于群组A数据
        assit[i++] = arr[p1++];
      }
    }

    // 群组A没有数据了，将群组B的数据填入辅助数组中
    if (p1 > mid) {
      while (p2 <= end) {
        assit[i++] = arr[p2++];
      }
    }

    // 群组B没有数据了，将群组A的数据填入辅助数组中
    if (p2 > end) {
      while (p1 <= mid) {
        assit[i++] = arr[p1++];
      }
    }

    // 将辅助数组中的数据拷贝到原数组中
    System.arraycopy(assit, start, arr, start, end - start + 1);
  }

  /**
   * 比较两个元素
   *
   * @return true：第一个元素大于第二个元素；false：第一个元素不大于第二个元素
   */
  private static boolean greater(Comparable v, Comparable w) {
    return v.compareTo(w) > 0;
  }

}