合併排序(Merge Sort)

此演算法為Divide and Conquer又稱為分而治之的經典範例

如下圖所示，合併排序是將原始數組不斷地二分分割，直到各個子數組都只剩下一個元素，然後再將這些子數組合併在一起排序，最後得到有序的數組。

虛擬碼

首先，如果傳入的數組長度小於等於1，則直接返回數組本身。如果不是，則將數組分為左半部分和右半部分，分別遞迴調用mergeSort()函數排序，最後將兩個排序好的數組合併在一起。

function mergeSort(arr):
    if arr.length <= 1:
        return arr
    else:
        mid = arr.length / 2
        left = arr[0...mid]
        right = arr[mid...end]
        return merge(mergeSort(left), mergeSort(right))

在merge()函數中，創建一個空的結果數組，然後不斷將左半部分和右半部分的第一個元素進行比較，將較小的元素添加到結果數組中，直到左半部分或右半部分全部添加到結果數組中。最後將剩餘的元素添加到結果數組中。

function merge(left, right):
    result = []
    while left and right are not empty:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right

程式碼

function 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);
}

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

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

複雜度

時間複雜度

$O(nlogn)$

因為每次將數組分成兩半進行排序，並且在合併的過程中需要遍歷整個數組，所以時間複雜度是O(n log n)。

空間複雜度

$O(n)$

因為需要額外創建兩個數組來存儲左半部分和右半部分，所以空間複雜度是O(n)

實戰

912. Sort an Array

給你一個整數陣列nums，請將陣列以升序排列並返回。您必須在O(nlog(n))時間複雜度內解決此問題，並使用較小的空間複雜度。

code

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    function merge(left, right){
        let result = []
        while(left.length > 0 && right.length > 0){
            if (left[0] > right[0]){
                result.push(right.shift())
            } else {
                result.push(left.shift())
            }
        }
        return result.concat(left, right)
    }

    if (nums.length <= 1) return nums
    let mid = Math.floor(nums.length / 2)
    let left = nums.slice(0, mid)
    let right = nums.slice(mid)
    return merge(sortArray(left), sortArray(right))
};