3.归并排序

1.什么是归并排序？

归并：将两个有序数组合并成一个更大的有序数组。

归并排序有两个主要操作：递归和合并。
要将一个数组排序，可以先（递归的）将它分半分别排序，然后将结果归并起来，这就是归并排序。
我们知道递归的主要思想是分治思想，而这也是归并排序的思想。

2.归并的抽象方法

归并方法主要讲数组左侧（a[lo..mid]）和数组右侧(a[mid+1..hi])归并成一个有序的数组并将结果防止到a[lo..hi]中。
在下面的实现中，我们将借助一个辅助数组aux：

public static void merge(int[] a, int lo, int mid,int hi){
  // i代表mid左侧的角标，j代表mid右侧的角标，每次向数组a中放入左侧的元素时i++，向数组a中放入右侧的元素时j++
  int i = lo, j= mid;
  //将原数组复制到辅助数组中
  for(int k = lo;k <= hi; k++){
     aux[k] = a[k];
  }
  
  for(int k = lo; k <= hi; k++){
    //1.左侧用尽取右侧
    if(i > mid)  a[k] = aux[j++];
    //2.右侧取尽取左侧
    else if(j>hi) a[k] = aux[i++];
    //3.左侧元素大于右侧元素时取右侧
    else if(a[i] > a[j])  a[k] = aux[j++];
    //4.左侧元素小于右侧元素时取左侧
    else a[k] = aux[i++];    
  }
}

归并完成后，下面要实现递归，递归的顺序有两种方式：

1.自顶向下
2.自底向上

3.自顶向下的归并排序

public class Merge{
  private static int[] aux;
  public static void sort(int[] a){
   //一次性分配空间
    aux = new int[a.length];
    mergeSort(a,0,a.length - 1);
  }
  //递归方法
  private static void mergeSort(int[] a; int lo; int hi){
    //跳出递归的条件
    if(lo >= hi) return;
    int mid = lo + (hi - lo)/2;
    mergeSort(a,lo,mid);//将左侧排序
    mergeSort(a,mid,hi);//将右侧排序    
    merge(a,lo,mid,hi);//归并结果 
  }
}

4.自底向上的归并排序

这种实现方法比标准的递归代码量更少。首先我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个大小为4的数组），然后是八八归并...

public class MergeBU {
    public static void sort(int[] a) {
        int n = a.length;
        int[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }
}

自底向上的归并.png

自底向上的归并排序比较适合采用链表的数据，这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建新的链表结点）。

5.复杂度

对于长度为N的数组，归并排序所需的时间和NlogN成正比；它的主要缺点是：所需要的额外空间和N成正比。

参考资料：https://algs4.cs.princeton.edu/22mergesort/