归并排序详解

归并排序是一种执行归并操作的排序算法，该算法采用分而治之的方法。归并排序的实现由两种方案：

• 自上而下的递归
• 自下而上的迭代

1.算法步骤

自上而下

• 把数组分成两个数组A，B,如果A、B数组的长度len>1;
• 继续执行步骤1，直到数组不能再分割。
• 递归的对相邻已排序的两个数组，合并两数组。（其中如果数组中只有一个元素，则该数组是排序数组）

自下而上

• 把数组Arr分成个len数组，把相邻的元素进行合并，并把合并后的数组存储到数组中。
• 迭代执行步骤1的步骤,直到数组仅有一个元素
• 返回这个元素就是排序好的数组

2.算法演示流程

3.算法代码

//---------------------------------------------------------------------------
    // 自上而下的归并

    // 分割
    function margeSort(arr){
        var len = arr.length;
        if (len < 2) {
            return arr;
        }

        var midValue = Math.floor(len / 2);
        var leftArr = arr.slice(0, midValue);
        var rightArr = arr.slice(midValue);

        return merge(margeSort(leftArr), mergeSort(rightArr));

    }

    // 合并方法
    function merge(leftArr, rightArr){

        var result = [];

        while(leftArr.length && rightArr.length){
            if (leftArr[0] > rightArr[0]) {
                result.push(rightArr.shift());
            }else{
                result.push(leftArr.shift());
            }
        }

        while(leftArr.length){
            result.push(leftArr.shift());
        }

        while(rightArr.length){
            result.push(rightArr.shift());
        }

        return result;
    }

//---------------------------------------------------------------------------
    // 下而上的迭代
    function mergeSort(arr){
        var len = arr.length;
        if (len < 2) {
            return arr;
        }

        while(arr.length >= 1){
            arr = margeGroup(arr);
        }

        return arr[0];
    }

    // 分组
    function margeGroup(currentArr){
        var result = [];
        while(currentArr.length){
            var leftArr = currentArr.shift;
            var rightArr = []
            if (currentArr.length) {
                rightArr = currentArr.shift;
            }
            result.push(merge(leftArr, rightArr));
        }

        return result;
    }

    // 合并
    function merge(leftArr, rightArr){
        var result = [];

        while(leftArr.length && rightArr.length){
            if (leftArr[0] > rightArr[0]) {
                result.push(rightArr.shift());
            }else{
                result.push(leftArr.shift());
            }
        }

        while(leftArr.length){
            result.push(leftArr.shift());
        }

        while(rightArr.length){
            result.push(rightArr.shift());
        }

        return result;
    }