算法实现: 归并排序(merge sort)

[lewenweijia]

function mergeSort(arr) {
  function merge(leftArr, rightArr) {
    const ans = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
      if (leftArr[leftIndex] < rightArr[rightIndex]) {
    ans.push(leftArr[leftIndex]);
    leftIndex++;
      } else {
    ans.push(rightArr[rightIndex]);
    rightIndex++;
      }
    }

    while (leftIndex < leftArr.length) {
      ans.push(leftArr[leftIndex++]);
    }

    while (rightIndex < rightArr.length) {
      ans.push(rightArr[rightIndex++]);
    }

    return ans;
  }

  // base case
  if (arr.length === 1) return arr;

  const mid = arr.length / 2 | 0;
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

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

[lewenweijia]

其他记录

基于比较的排序算法理论时间复杂度最优?: O(nlogn) 归并的特点?: 适用于所有连续的? 而不是单单数组, 链表也是可以的哦 -> 问题: LC? 合并两个排序链表