归并排序

以下代码为个人笔记。

let tmp = []
function mergeSort (nums, l, r) {
  if (l >= r) {
    return
  }

  let mid = (l + r) >> 1;

  mergeSort(nums, l, mid)
  mergeSort(nums, mid + 1, r)

  let i = l,
    j = mid + 1
  let cnt = 0

  while (i <= mid && j <= r) {
    if (nums[i] < nums[j]) {
      tmp[cnt++] = nums[i++]
    } else {
      tmp[cnt++] = nums[j++]
    }
  }

  while (i <= mid) {
    tmp[cnt++] = nums[i++]
  }

  while (j <= r) {
    tmp[cnt++] = nums[j++]
  }

  for(let i = 0; i < r - l + 1; i++) {
    nums[i+l] = tmp[i]
  }
}

const nums = [5,2,3,1]
mergeSort(nums, 0, nums.length - 1);
console.log(nums);