编写一个函数，实现归并排序

推荐答案

// www.javascriptcn.com code example
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

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

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

function merge(left, right) {
    let 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));
}

本题详细解读

归并排序的基本思想

归并排序是一种分治算法，它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排序后的子数组合并成一个有序的数组。归并排序的核心思想是“分而治之”，即通过递归将问题分解为更小的子问题，直到子问题足够简单可以直接解决。

代码解析

1. mergeSort 函数：

   • 首先检查数组的长度，如果长度小于等于1，则直接返回数组，因为一个元素或空数组已经是有序的。
   • 然后找到数组的中间位置，将数组分成左右两个子数组。
   • 递归地对左右子数组进行排序，最后调用 merge 函数将两个有序的子数组合并成一个有序的数组。

2. merge 函数：

   • 创建一个空数组 result 用于存储合并后的结果。
   • 使用两个指针 leftIndex 和 rightIndex 分别遍历左右两个子数组。
   • 比较左右子数组中的元素，将较小的元素放入 result 数组中，并移动相应的指针。
   • 当其中一个子数组遍历完后，将另一个子数组中剩余的元素直接拼接到 result 数组的末尾。

时间复杂度

归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。这是因为每次递归都将数组分成两半，递归深度为 log n，而每一层的合并操作需要 O(n) 的时间。

空间复杂度

归并排序的空间复杂度为 O(n)，因为需要额外的空间来存储合并后的数组。

稳定性

归并排序是一种稳定的排序算法，因为在合并过程中，相同元素的相对顺序不会改变。