归并排序/Merge Sort ✓

归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

//将数组分治， 将分治的数组排序，将有序的数组合并
const merge = (left, right) => {
    let result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left, right);
}

/**
 * 归并排序
 * 将数组递归分成左右两个数组，直到数组只剩一个元素
 * 将分完的数组，依次按大小合并
 */
const mergeSort = (arr) => {
    if (arr.length <= 1) {
        return arr;
    }
    let midIndex = Math.floor(arr.length / 2);
    let left = arr.slice(0, midIndex);
    let right = arr.slice(midIndex);
    return merge(mergeSort(left), mergeSort(right));
}

Try in StackBlitz

空间复杂度

O(n)

时间复杂度

O(nlogn)

是否是稳定排序

是