归并排序

归并排序算法思想

tip

1. 分解：将数组分解成越来越小的半子数组，直到每个子数组只有一个元素。
2. 解决：递归地排序每个子数组，但实际上这些子数组在初始时就已经是有序的（因为只有一个元素）。
3. 归并：将两个有序子数组合并成一个有序数组。这一步是归并排序的核心。

归并排序算法步骤

假设数组的长度为 $n$。

1. 分解：
   1. 当 $n \leq 1$，直接返回原数组
   2. 找到当前数组的中点 middle, middle = Math.floor(n / 2)。
   3. left 为 middle 左边的数组，right 为 middle 右边的数组。
   4. 递归地对 left 和 right 分别调用分解函数。
   5. 最后用合并函数将排好序的 left 和 right 合并为一个排好序的数组。
2. 归并：因为递归地调用了分解，因此我们会从单个元素的 left 和 right 开始进行归并。
   1. 使用 nums 来存放排好序的数组。
   2. 使用两个指针 leftPointer 和 rightPointer 分别指向 left 和 right 的起始位置。
   3. 当两个指针都没有到达末尾的时候，将 left[leftPointer] 和 right[rightPointer] 中小的那个元素插入 nums，并且对应的指针 + 1。
   4. 将指针没到达末尾的那个数组的剩余部分直接插入 nums。
   5. 返回 nums。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  return mergeSort(nums);
};

function mergeSort(nums) {
  if(nums.length <= 1) {
    return nums;
  }

  const length = nums.length;
  const middle = Math.floor(length / 2);
  const left = nums.slice(0, middle);
  const right = nums.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let leftPointer = 0;
  let rightPointer = 0;
  const result = [];
    
  while(leftPointer < left.length && rightPointer < right.length) {
    if(left[leftPointer] <= right[rightPointer]) {
      result.push(left[leftPointer]);
      leftPointer ++;
    } else {
      result.push(right[rightPointer]);
      rightPointer ++;
    }
  }
    
  while(leftPointer < left.length) {
    result.push(left[leftPointer]);
    leftPointer ++;
  }
    
  while(rightPointer < right.length) {
    result.push(right[rightPointer]);
    rightPointer ++;
  }
    
  return result;
}

复杂度

• 时间复杂度：$O(n \log n)$。
• 空间复杂度：$O(n)$。

排序稳定性

因为在两个有序子数组的归并过程中，如果两个有序数组中出现相等元素，merge(leftPointer, rightPointer); 算法能够使前一个数组中那个相等元素先被复制，从而确保这两个元素的相对顺序不发生改变。因此，归并排序算法是一种稳定排序算法。