[算法]归并排序

思想： 分而治之

特点： 快，稳定

步骤：

1. 分割数组， 直到只有一个元素
2. 合并两个有序数组

时间复杂度O(nlogn)
空间复杂度O(n)

js实现

function merge (left, right) {
  // Merge sorted array
  let res = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  return [...res, ...left, ...right];
}
function mergeSort(arr) {
  const len = arr.length;
  if (len < 2) return arr;
  const half = len / 2;
  const left = arr.splice(0, half)
  return merge(mergeSort(left), mergeSort(arr));
}

代码：https://github.com/zhaocchen/leetcode/blob/master/sort/mergeSort.js

剑指 Offer 51. 数组中的逆序对

关键：分治的两部分数组，分别维护两个指针从头遍历

• 左边区间的逆序对；
• 右边区间的逆序对；
• 横跨两个区间的逆序对

统计两个有序列表的逆序对

function reversePairs(nums1: number[], nums2: number[]): number {
    let i: number = 0, j: number = 0;
    let count: number = 0;
    while(i < nums1.length && j < nums2.length) {
        if (nums1[i] > nums2[j]) {
            ++j;
            count += (nums1.length - i);
        } else {
            ++i;
        }
    }
    return count;
}
console.log(reversePairs([2, 3, 6, 7], [0, 1, 4, 5])); // 12

完整

function reversePairs(nums: number[]): number {
    let count: number = 0;
    const n: number = nums.length;
    if (n < 2) return 0;

    function merge(nums: number[], left: number, mid: number, right: number): void {
        let n: number = right - left + 1;
        let t: number[] = new Array(n);
        let i: number = left, j: number = mid + 1, idx: number = 0;
        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                count += (mid - i + 1);
                t[idx++] = nums[j++];
            } else {
                t[idx++] = nums[i++];
            }
        }
        while (i <= mid) {
            t[idx++] = nums[i++];
        }
        while (j <= right) {
            t[idx++] = nums[j++];
        }
        for (let k: number = 0; k < n; ++k) {
            nums[left + k] = t[k];
        }
    }

    function mergeSort(nums: number[], left: number, right: number): void {
        if (left == right) return;
        let mid: number = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    mergeSort(nums, 0, n - 1);
    return count;
};

LC

148. 排序链表

快慢指针 + 归并排序