归并排序详解

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

1. 自上而下的递归
2. 自下而上的迭代

1.算法步骤

自上而下

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

自下而上

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

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