05_归并排序

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素,然后将数组排序合并,最终合并为排序好的数组。

点击查看代码
function mergeSort(arr) {
  if (!Array.isArray(arr) || arr.length == 0) return;
  if (arr.length == 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2),
    leftArr = arr.slice(0, mid),
    rightArr = arr.slice(mid, arr.length);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

function merge(left, right) {
  let result = [],
    leftLength = left.length,
    rightLength = right.length,
    lf = 0,
    lr = 0;
  while (lf < leftLength && lr < rightLength) {
    if (left[lf] > right[lr]) {
      result.push(right[lr++]);
    } else {
      result.push(left[lf++]);
    }
  }
  while (lf < leftLength) {
    result.push(left[lf]);
    lf++;
  }
  while (lr < rightLength) {
    result.push(right[lr]);
    lr++;
  }
  return result;
}
Last Updated:
Contributors: hqchqc