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);
      mergeInPlace(arr, left, mid, right);
      left = left + 2 * step;
    }
    step *= 2;
  }
  return arr;
}

function mergeInPlace(arr, start, mid, end) {
  const left = arr.slice(start, mid);
  const right = arr.slice(mid, end);
  let i = 0;
  let j = 0;
  let k = start;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      arr[k] = left[i];
      i++;
    } else {
      arr[k] = right[j];
      j++;
    }
    k++;
  }

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

  while (j < right.length) {
    arr[k] = right[j];
    j++;
    k++;
  }
}

性能特点

• 时间复杂度：O(n log n) 在所有情况下
• 空间复杂度：O(n) 需要额外空间存储临时数组
• 稳定排序：相等元素的相对位置不会改变

使用示例

const array = [5, 3, 8, 4, 2, 7, 1, 10];
console.log(mergeSort(array)); // [1, 2, 3, 4, 5, 7, 8, 10]
console.log(mergeSortIterative(array.slice())); // 同样结果

优化建议

对于小规模数组（通常n<15），可以切换到插入排序以提高性能。合并过程可以使用双指针技术减少内存分配。