深刻理解归并排序

「归并排序」核心就是每个数组「两两比较」并合并，直至只剩下一个数组。

我们通过图片的方式，来排序一个数组为例：

这里有六个数字，我们第一步先将一个数组视为一组，并对相邻的两组进行「两两比较」。可以得到如下：

再进行两两比较，如下：

最后进行一次两两比较结束，如下：

附上 Java 代码：

public class MyMegerSort {
    // 归并排序
    public int[] sortArray(int[] nums) {
        int length = nums.length;
        // src 代表将要排序的数组，dst 表示将排序结果暂存的数组
        int[] src = nums;
        int[] dst = new int[length];

        // base 代表一个单位的数组的大小，并且每次增大一倍
        // * 「归并排序」核心就是每个数组「两两比较」并合并，直至只剩下一个数组
        // base 的大小是已排序好的数组大小
        for (int base = 1; base < length; base += base) {
            for (int start = 0; start < length; start += base * 2) {
                int mid = Math.min(start + base, length);
                int end = Math.min(start + base * 2, length);

                // index1、index2 分别代表着将要对比的两个数组的头节点。分别为左数组头节点和右数组头节点
                // k 用于表示 dst 的下标，含义为排序到的下标位置
                int index1 = start, index2 = mid, k = start;
                // 归并排序核心代码。遍历这两个排好序的数组，每次将一个最小的节点插入 dst 数组
                while (index1 < mid || index2 < end) {
                    if (index2 == end || (index1 < mid && src[index1] < src[index2])) {
                        dst[k++] = src[index1++];
                    } else {
                        dst[k++] = src[index2++];
                    }
                }
            }

            // 交换两个数组 或 为 dst 数组开辟新的数组空间
            int[] temp = src;
            src = dst;
            dst = temp;
        }

        return src;
    }
}

最后附上图片来源：「数据结构——三分钟搞定归并排序」