归并排序

采用分治思想，将数组不断二分，然后合并有序子数组。

思路

• 分解：递归地将数组二分为左右两部分，直到每部分只有一个元素
• 合并：将两个有序数组合并为一个有序数组
  • 比较两个数组的首元素，取较小的放入结果数组
  • 重复直到一个数组为空
  • 将剩余元素直接拼接到结果数组
• 使用位运算 len >> 1 计算中点，等价于 Math.floor(len / 2)

代码

// 归并排序
// 一直二分，再比较排序

function mergeSort(arr){
    function merge(left, right){
        let result = [];
        while(left.length && right.length){
            if(left[0] < right[0]){
                result.push(left.shift());
            }
            else{
                result.push(right.shift());
            }
        }
        while(left.length){ //此处把剩下的部分直接放进result
            result.push(left.shift());
        }
        while(right.length){
            result.push(right.shift());
        }
        return result; //可以直接result.concat(left, right)
    }
    let len = arr.length;
    if(len === 1){
        return arr;
    }
    let mid = len >> 1; // Math.floor(len / 2)
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right))
}

复杂度

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定