归并排序

概要

归并排序，利用分治思想，将大的数组，分解为小数组，直至单个元素。然后，使用选择排序的方式，对分拆的小数组，进行回溯，并有序合并，直至合并为一个大的数组。

效果图

小数组合并的过程

解法

function mergeSort(arr){

    return sort(arr, 0, arr.length - 1); // 注意右区间是arr.length - 1

    // sort方法，进行递归
    function sort(arr, left, right){
        
        // 当left !== right时，证明还没分拆到最小元素
        if(left < right){
            // 取中间值，分拆为两个小的数组
            const mid = Math.floor((left+right) / 2);
            const leftArr = sort(arr, left, mid);
            const rightArr = sort(arr, mid+1, right);
            // 递归合并
            return merge(leftArr, rightArr)
        }

        // left == right, 已经是最小元素，直接返回即可
        return left >= 0 ? [arr[left]] : [];
    }

    // 合并两个有序数组
    function merge(leftArr, rightArr){
        let left = 0;
        let right = 0;
        const tmp = [];

        // 使用双指针，对两个数组进行扫描
        while(left < leftArr.length && right < rightArr.length){
            if(leftArr[left] <= rightArr[right]){
                tmp.push(leftArr[left++]);
            }else{
                tmp.push(rightArr[right++]);
            }
        }

        // 合并剩下的内容
        if(left < leftArr.length){
            while(left < leftArr.length){
                tmp.push(leftArr[left++]);
            }
        }

        if(right < rightArr.length){
            while(right < rightArr.length){
                tmp.push(rightArr[right++]);
            }
        }

        return tmp;
    }

}

参考

• 图解排序算法(四)之归并排序