js实现并轨排序

并轨排序（Merge Sort）实现

并轨排序是一种分治算法，通过递归将数组拆分为更小的子数组，排序后再合并。以下是JavaScript的实现方式：

递归实现

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

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

非递归实现（迭代法）

function mergeSortIterative(arr) {
  let step = 1;
  const n = arr.length;

  while (step < n) {
    let left = 0;
    while (left < n - step) {
      const mid = left + step;
      const right = Math.min(left + 2 * step, n);
      merge(arr, left, mid, right);
      left = left + 2 * step;
    }
    step *= 2;
  }
  return arr;
}

function merge(arr, left, mid, right) {
  const temp = arr.slice(left, mid);
  let i = 0, j = mid, k = left;

  while (i < temp.length && j < right) {
    arr[k++] = temp[i] <= arr[j] ? temp[i++] : arr[j++];
  }

  while (i < temp.length) {
    arr[k++] = temp[i++];
  }
}

算法分析

时间复杂度始终为O(n log n)，空间复杂度为O(n)。是稳定排序算法，适合大数据量排序。递归实现代码更简洁，但迭代实现避免了递归调用栈的开销。

使用示例

const arr = [5, 3, 8, 4, 2, 7, 1, 10];
console.log(mergeSort(arr)); // [1, 2, 3, 4, 5, 7, 8, 10]