用javascript语言写一个归并排序

归并排序是一种分治算法，它的基本思路是将待排序的数组递归地分成两半，直到每个子数组只有一个元素，然后再将排好序的子数组归并起来，最终得到一个有序的数组。

下面是用 JavaScript 实现归并排序的代码示例：

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

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

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

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

使用方法：

const sortedArray = mergeSort([5, 3, 1, 2, 4]);
// sortedArray 现在是 [1, 2, 3, 4, 5]

归并排序的时间复杂度为 O(n * logn)，空间复杂度为 O(n)，它的时间复杂度比较优秀，但是由于需要额外的存储空间，因此在某些情况下并不是最优的选择。