1. 归并排序

什么是归并排序？
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

1.2 时空复杂度

时间复杂度：O(n㏒₂n)、最好/坏均是。
空间复杂度：O(n)
稳定性：稳定（相同元素排序后相对位置不变）

1.3 动图演示

1.4 算法实现

递归法实现：

public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

归并排序迭代版：

package MergeSort;
import Utils.SortUtils;

public class MergeSort {

    public static void mergeSort(int[] a){
        int[] TR = new int[a.length];//用于存放归并结果

        int k=1;//起始，子序列长度为1
        while(k<a.length){
            mergePass(a, TR, k, a.length);//将原先无序的数据两两归并入TR
            k = 2*k;//子序列长度加倍
            mergePass(TR, a, k, a.length);//将TR中已经两两归并的有序序列再归并回数组a
            k = 2*k;//子序列长度加倍
        }
    }

    public static void mergePass(int[] SR, int [] TR,int s,int len){

        int i=0;
        while (i < len-2*s+1) {//8
            merge(SR,TR,i,i+s-1,i+2*s-1);//两两归并
            i=i+2*s;
        }

        //处理最后的尾数
        //i=8
        if(i< len-s+1){//9
            merge(SR, TR, i, i+s-1, len-1);//归并最后两个序列
        }else {
            for (int j = i; j < len; j++) {//若最后只剩下单个子序列
                TR[j] = SR[j];
            }
        }   
    }

    public static void merge(int[] SR,int[] TR,int i,int m,int n){
        int j,k,l;

        //i(0~4) j(5~8)
        for(j=m+1,k=i; i<=m && j<=n; k++){

            if(SR[i]<SR[j]){
                TR[k] = SR[i++];
            }else{
                TR[k] = SR[j++];
            }
        }


        if(i<=m){
            for (l = 0; l <= m-i ; l++) {
                TR[k+l] = SR[i+l];
            }
        }

        if(j<=n){
            for (l = 0; l <= n-j; l++) {
                TR[k+l] = SR[j+l];
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {2,3,5,4,1,6,9,8,7,10,20,45,32,28,44,31,55,43,23,21,23,21,33,21};
        mergeSort(a);
        SortUtils.printString(a);
    }
}

2. 总结

归并排序的优缺点：

优点

1.归并排序的效率达到了巅峰：时间复杂度为O(nlogn)，这是基于比较的排序算法所能达到的最高境界
2.归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要
3.归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序…）