归并排序

归并字面上的意思是合并，归并算法的核心思想是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。
上述的这种表述只是其中一种归并排序算法，亦称自顶向下的归并排序。

自顶向下的归并排序

图片源自：https://www.cnblogs.com/nullzx/p/5968170.html

image.png

Python代码（源自Python编程导论）：

def merge(left, right, compare):
    """
    假设left和right是两个有序列表，compare定义了一种元素排序规则。
    返回一个新的有序列表（按照compare定义的顺序），其中包含与(left+right)相同的元素。
    """
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

def mergeSort(L, compare = lambda x, y: x<y):
    """
    假设L是列表，compare定义了L中元素的排序规则
    返回一个新的具有L中相同元素的有序列表
    """
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L) // 2
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

Java代码（源自微信公众号五分钟学算法）：

public static void sort(int[] arr) {
    int[] tempArr = new int[arr.length];
    sort(arr， tempArr， 0， arr.length-1);
}

/**
 * 归并排序
 * @param arr 排序数组
 * @param tempArr 临时存储数组
 * @param startIndex 排序起始位置
 * @param endIndex 排序终止位置
 */
private static void sort(int[] arr，int[] tempArr，int startIndex，int endIndex){
    if(endIndex <= startIndex){
        return;
    }
    //中部下标
    int middleIndex = startIndex + (endIndex - startIndex) / 2;

    //分解
    sort(arr，tempArr，startIndex，middleIndex);
    sort(arr，tempArr，middleIndex + 1，endIndex);

    //归并
    merge(arr，tempArr，startIndex，middleIndex，endIndex);
}

/**
 * 归并
 * @param arr 排序数组
 * @param tempArr 临时存储数组
 * @param startIndex 归并起始位置
 * @param middleIndex 归并中间位置
 * @param endIndex 归并终止位置
 */
private static void merge(int[] arr， int[] tempArr， int startIndex， int middleIndex， int endIndex) {
    //复制要合并的数据
    for (int s = startIndex; s <= endIndex; s++) {
        tempArr[s] = arr[s];
    }

    int left = startIndex;//左边首位下标
    int right = middleIndex + 1;//右边首位下标
    for (int k = startIndex; k <= endIndex; k++) {
        if(left > middleIndex){
            //如果左边的首位下标大于中部下标，证明左边的数据已经排完了。
            arr[k] = tempArr[right++];
        } else if (right > endIndex){
            //如果右边的首位下标大于了数组长度，证明右边的数据已经排完了。
            arr[k] = tempArr[left++];
        } else if (tempArr[right] < tempArr[left]){
            arr[k] = tempArr[right++];//将右边的首位排入，然后右边的下标指针+1。
        } else {
            arr[k] = tempArr[left++];//将左边的首位排入，然后左边的下标指针+1。
        }
    }
}

我们可以发现 merge 方法中只有一个 for 循环，直接就可以得出每次合并的时间复杂度为 O(n) ，而分解数组每次对半切割，属于对数时间 O(log n) ，合起来等于 O(log2n) ，也就是说，总的时间复杂度为 O(nlogn) 。
关于空间复杂度，其实大部分人写的归并都是在 merge 方法里面申请临时数组，用临时数组来辅助排序工作，空间复杂度为 O(n)，而我这里做的是原地归并，只在最开始申请了一个临时数组，所以空间复杂度为 O(1)。

自底向上的归并排序

（源自：https://www.cnblogs.com/nullzx/p/5968170.html）
自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，然后四个四个有序的序列归并八个八个有序的序列，以此类推，直到，归并的长度大于整个数组的长度，此时整个数组有序。需要注意的是数组按照归并长度划分，最后一个子数组可能不满足长度要求，这个情况需要特殊处理。自顶下下的归并排序算法一般用递归来实现，而自底向上可以用循环来实现。

image.png

Java代码

public static void sortDownToUp(int[] a) {
    int[] aux = new int[a.length];
    for (int sz = 1; sz < a.length; sz *= 2) {
        for (int lo = 0; lo < a.length - sz; lo += 2 * sz) {
            merge(a, aux, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1,a.length - 1));
        }
    }
}

private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) {
            a[k] = aux[j++];
        } else if (j > hi) {
            a[k] = aux[i++];
        } else if (aux[j] < aux[i]) {
            a[k] = aux[j++];
        } else {
            a[k] = aux[i++];
        }
    }
}

关于自底向上归并排序的应用，见用于链表的排序：https://www.jianshu.com/p/2b9ae3416099