由mergeSort引发的一些思考

重新梳理一下归并排序以及一些相关的东西。

对于归并排序大家如果需要回忆下是个什么东西的话，可以点击这个链接，里面有各种排序的动画演示以及讲解，比我再用文字赘述一遍要好得多，功能相当强大。

先给出归并排序的 js 代码实现：

function mergeSort(arr, l, r) {if (l === r) {return;}
    let mid = Math.floor((r + l) / 2);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    while(leftIndex <= mid && rightIndex <= r) {let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {helpArr.push(leftItem);
            leftIndex++;
        } else {helpArr.push(rightItem);
            rightIndex++;
        }
    }

    // 这俩循环只会进去一个，因为经过上面的比较，要么左边部分走完了，要么右边部分走完了
    while(leftIndex <= mid) {helpArr.push(arr[leftIndex]);
        leftIndex++;
    }

    while(rightIndex <= r) {helpArr.push(arr[rightIndex]);
        rightIndex++;
    }

    for (let index = 0; index < helpArr.length; index++) {arr[l] = helpArr[index];
        l++;
    }
}

如何估计归并排序的时间复杂度呢？

由于上面采用了递归写法，我们使用 master 公式对递归进行时间复杂度估算，以下是公式详情。
<p>T(n) = a*T(n/b) + O(n^d)<br/>
（1）、log(b, a) > d => 复杂度为 O(n^log(b, a))<br/>
（2）、log(b, a) = d => 复杂度为 O(n^d*logn)<br/>
（3）、log(b, a) < d => 复杂度为 O(n^d)</p>

a 代表递归的次数，由于在 mergeSort 中调用了两次 mergeSort，所以归并排序中 a = 2。<br/>
b 代表样本量被划分几份，由于我们对样本量是一分为二将数组分为 left 和 right 部分，所以归并排序中 b = 2。<br/>
O(n^d) 代表其他操作的时间复杂度，所以在归并排序中主要是 merge 这个函数，相当于是执行了一次数组遍历，则为 O(n)。<br/>
a = 2，b = 2，d = 1 根据 master 公式，复杂度为 nlogn。

我们知道冒泡排序、选择排序、插入排序的时间复杂度都是 O(n^2)，当样本量比较大的时候，n^2 比之 nlogn 差了可不是一星半点。这是为什么呢？因为在其他三种排序中，会浪费元素之间的比较，比如冒泡排序冒泡比较一轮只定位了一个元素，下一轮冒泡又只定位一个元素，会浪费元素之间的相互比较；而归并排序通过分治，由小到大进行比较合并的过程中，上一次比较合并的元素不会再次发生比较，有序的区域成规模增长，这样就不会浪费比较，节省了时间。

由归并排序引入数组小和问题和数组逆序对问题。

根据小和的题目要求，我们思考一下可以发现，在归并排序过程中，left 和 right 部分进行比较合并的时候，其实就可以找到左边部分比右边部分小的数，意思就是说我们可以很方便的在 merge 这个函数执行过程中来计算数组的小和且会快很多，因为合并的时候左右两遍都是有序的，如果一个数比右边的第一个数字小，我们可以得知这个数字肯定比右边全部的数字都小。

举个例子，比如 left = [1,2,3]，right = [4,5,6]，1 小于 4，说明右边三个数都比 1 大，假如说小和等于 sum，那么 sum 就要加 1 * 3。

代码实现一下小和：

function smallSum(arr) {if (!arr || arr.length < 2) {return 0;}
    return mergeSort(arr, 0, arr.length - 1);
}

function mergeSort(arr, l, r) {if (l === r) {return 0;}
    let mid = Math.floor((l + r)/2);
    return mergeSort(arr, l, mid)
            + mergeSort(arr, mid + 1, r)
            + merge(arr, l, mid, r)
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    let sum = 0;
    while(leftIndex <= mid && rightIndex <= r) {let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {
            /** 相对于归并排序增加的部分 **/
            let tempSum = (r - rightIndex + 1) * leftItem
            sum += tempSum;
            /***************************/
            helpArr.push(leftItem);
            leftIndex++;
        } else {helpArr.push(rightItem);
            rightIndex++;
        }
    }

    /** 这部分和归并排序 merge 函数一样 **/

    return sum;
}

对于小和都知道如何使用归并排序进行求解之后，逆序对其实和小和是一样的，只是反过来了而已，以下直接贴出代码。

function inversePairs(arr) {if (!arr || arr.length < 2) {return [];
    }
    return mergeSort(arr, 0, arr.length - 1);
}

function mergeSort(arr, l, r) {if (l === r) {return [];
    }
    let mid = Math.floor((l + r)/2);
    return [...mergeSort(arr, l, mid),
        ...mergeSort(arr, mid + 1, r),
        ...merge(arr, l, mid, r)
    ];
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    let res = [];
    while(leftIndex <= mid && rightIndex <= r) {let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {helpArr.push(leftItem);
            leftIndex++;
        } else {
            /** 相对于归并排序增加的部分 **/
            res.push([leftItem, rightItem]);
            /***************************/
            helpArr.push(rightItem);
            rightIndex++;
        }
    }

    /** 这部分和归并排序 merge 函数一样 **/

    return res;
}

以上是对归并排序这部分内容进行的一些回顾和总结，希望能加深自己对它的理解，能在其他更多的地方将其运用上；如果有不正确的地方，大家可以踊跃指出，我将及时改正。