第 10 关 | 天上的明月——快速排序和归并排序: 3.黄金挑战—

1. 归并排序原理

归并排序（MERGE-SORT）简单来说就是把大的序列先视为若干个比较小的数组，分成几个比较小的结构，然后利用归并的思想实现的排序方法，该算法采用经典的分治策略（就是把问题分（divide）成一些小的问题进行求解，而治（conquer）就是把分的阶段得到的各个答案"合"在一起）。

可以看到这种结构很像两棵套在一起的满二叉树。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。就是图中上面侧的满二叉树。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，就是下侧的满二叉树。比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，这个操作与合并两个有序数组的完全一样，不同的是这里是将数组的两个部分合并。

再看一下遍历时处理元素的过程：

private static void merge_sort(int[] arr, int l, int r) {
    // 递归结束条件
    if (l >= r) return;

    // 以下都为逻辑部分
    int mid = l + ((r - l) >> 1);
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);

    int[] tmp = new int[r - l + 1]; // 临时数组, 用于临时存储 [l,r]区间内排好序的数据
    int i = l, j = mid + 1, k = 0;  // 两个指针
    // 进行归并
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) 
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];

    // 进行赋值
    for (i = l, j = 0; i <= r; i++, j++)
    arr[i] = tmp[j];
}

第 10 关 | 天上的明月——快速排序和归并排序: 3.黄金挑战——归并排序-灵析社区

1. 归并排序原理