JavaScript 排序算法之归并排序

Question

归并排序（稳定）

算法分析：

最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作(Merge)，也叫归并算法，指的是 将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

步骤：
当我们有两个排好序的数组，我们会逐一比较他们的每个项，将其中一个数组合并到另一个数组中（注意，不再开辟额外的存储空间）。
想象有两个有序序列A和B ，并将B合并到A中。比较A[0]和B[0]，如果A[0]较大，将B[0]插入到A[0]前（插入排序）；如果B[0]较大，说明A[0]位置无需变化，即合并后的排列，继续比较A[1]和B[0]。重复此步骤，直到B中的序列长度为0，全部合并到A中。

那么我们如何达到有两个排好序的数组的状态？
有多个项的数组除非排好序，否则无法进行比较。我们可以 通过递归拆分数组，直到我们能比较多对单一项的时候为止。

function mergeSort(arr) {
    function sort(arr, first = 0, last = arr.length - 1) {
        if(last - first < 1) return; // last - first
        let middle = Math.floor((first + last) / 2);
        sort(arr, first, middle);
        sort(arr, middle + 1, last);
        
        let f = first;
        let l = last;
        let m = middle;
        while(f <= m && m + 1 <= l) {
            if(arr[f] >= arr[m + 1]) { // >= 表示m+1是两个子序列中的最小数 把这个数合并到第一位
                let temp = arr[m + 1];
                for(let i = m; i >= f; i--) {
                    arr[i + 1] = arr[i]; // i
                }
                arr[f] = temp; // 让最小的数已经移到 f 位置
                m++; // 此时合并序列增添了一位数，往后移继续对比两两子序列
            } else {
                f++; // 两个子序列中最小数就是 f ，忽略 f ，后移继续对比
            }
        }
        return arr;
    }
    return sort(arr);
}