思路分析

归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。

图解

代码示例

1）递归方法

//有两个重要的特点，可以适用于外部排序（数据在磁盘上），也可以适用于链表排序
// （希尔，堆排序，快速排序依赖随机访问能力，都不适合链表排序）
//基本思路来源于基本问题：把两个有序链表/数组合并成一个

//[low,mid) 有序区间
//[mid,high) 有序区间
//两个区间进行合并
public static void  merge(int[] array,int low, int mid, int high){
    int[] output = new int[high - low];
    int outputIndex = 0;//记录当前output数组中被放入了多少元素 
    int cur1 = low;//第一个区间的起始下标 
    int cur2 = mid;//第二个区间的起始下标

    while (cur1 < mid && cur2 < high){
        //以下条件写成小于等于，才能保证稳定性 
        if (array[cur1] <= array[cur2]){
            output[outputIndex] = array[cur1];
            outputIndex++;
            cur1++;
        }else {
            output[outputIndex] = array[cur2];
            outputIndex++;
            cur2++;
        }
    }
    //当以上循环结束的时候，肯定有一个cur到达末尾，另一个还剩下一些内容 
    //把剩余的内容老被到output中 
    while (cur1 < mid){
        output[outputIndex] = array[cur1];
        outputIndex++;
        cur1++;
    }
    while (cur2 < high){
        output[outputIndex] = array[cur2];
        outputIndex++;
        cur2++;
    }

    //把output的元素搬运到原来的数组 
    for (int i = 0; i < high - low; i++){
        array[low + i] = output[i];
    }

}

public static void mergeSort(int[] array){
    mergeSortHelper(array,0,array.length);
}

//[low,high)前闭后开区间
private static void mergeSortHelper(int[] array, int low, int high) {
    if (high - low <= 1){
        return;
    }
    int mid = (low + high) / 2;
    mergeSortHelper(array,low,mid);
    mergeSortHelper(array,mid,high);

    //当我们把左右区间归并排序完了，说明左右区间已经是有序区间了
    merge(array,low,mid,high);
}

2）非递归方法

public static void mergrSortByLoop(int[] array){
    //引入一个gap变量进行分组 
    //当gap为1的时候，0 1是一组  2 3是一组  4 5是一组。。。 
    //当gap为2的时候，就是[0，1]和【2，3】是一组。。。。 
    //当gap为4的时候，【0，1，2，3】和【4，5，6，7】是一组 
    for (int gap = 1; gap < array.length; gap *= 2){
        //接下来进行具体的分组合并 
        for (int i = 0; i < array.length; i+= 2*gap){
            int beg = i;
            int mid = i + gap;
            int end = i + 2*gap;
            //防止下标越界 
            if (mid > array.length){
                mid = array.length;
            }
            if (end > array.length){
                end = array.length;
            }
            merge(array,beg,mid,end);
        }
    }
}

性能分析

时间复杂度： O(n * log(n))

空间复杂度： O(n)

稳定性： 稳定排序