js归并排序算法的原理及简单demo

最近看了一道“如何给阿里两万多名员工按照年龄排序”的面试题后，很想记录下来自己的解题思路，下面：
综合考虑到基数较大和稳定性，我们采取归并排序的算法；
归并算法分为两个两个灵魂步骤，即：拆分=>归并；
我们先把两万多名员工的基数缩小至六名员工的基数，他们的年龄数组未排序前为[25,18,17,31,25,30],我们实现第一个灵魂操作，拆分:
归并算法的拆分思想是将一个数组一分为二，然后将分出来的数组继续一分为二，直至出现单个数组的长度为1，不可再分为止；

如上图，一个长度为6的数组按照左右结构一直拆分至6个长度为1的数组，拆分就完毕了，这时我们由下往上回溯，将数组归并，图解：

六个长度为一的数组归并之后又变成了一个长度为6的数组，但是排序发生了改变，这就是归并算法，下面是代码实现：

我们一步一步来，第一步先来实现拆分的部分：

// 拆分
            function mergeSort(arr){
                console.log(`arr=${arr}`)
                if(arr.length==1){//如果数组长度为1则返回数组
                    return arr
                }
                var mid=Math.floor(arr.length/2);//将数组一拆分为二
                var left=arr.slice(0,mid);
                var right=arr.slice(mid);
                 mergeSort(left);//如果数组长度不为1，则继续递归拆分，（由控制台可以看出递归会先将left执行完后再去执行right）
                 mergeSort(right)
            }
            console.log(mergeSort([25,18,17,31,25,30]))

控制台打印出结果：

这个时候我们可以看到，我们已经采用递归的方式将数组拆分为六个长度为一的数组了，接下来走第二步的合并，合并的思想是左右两个数组的第一个元素比较大小，然后将大的数（或者小的数）提取出来存放在一个第三方数组，直接上代码：

// 合并
            function merge(left,right){
                var arr=new Array;//新建一个第三方数组
                    if(left[0]<=right[0]){//比较left的第一位和right的第一位谁小，小的提取出来push进第三方数组
                        arr.push(left.shift())
                    }else{
                        arr.push(right.shift())
                    }    
                return arr.concat(left).concat(right)//将提取出来的数组和原数组归并成一个数组
            };
            console.log(merge([25],[30]))//代码到这一步只是展示了合并的原理和思路，并不完整，我们不急，先用简单的单元素数组进行排序合并，这也是合并的第一层合并

控制台打印出[25,30],说明我们的归并和排序都是成功的，下面我们将升级两个函数，使其能够正式地操作复杂的归并排序：

// 合并
            function merge(left,right){
                var arr=new Array;//新建一个第三方数组
                while(left.length>0&&right.length>0){////比较left的第一位和right的第一位谁小，小的提取出来push进第三方数组
                    if(left[0]<=right[0]){
                        arr.push(left.shift())
                    }else{
                        arr.push(right.shift())
                    }
                };
                return arr.concat(left).concat(right)//将提取出来的数组和原数组归并成一个数组
            };
            // 拆分
            function mergeSort(arr){
                console.log(`arr=${arr}`)
                if(arr.length==1){//如果数组长度为1则返回数组
                    return arr
                };
                var mid=Math.floor(arr.length/2);//将数组一拆分为二
                var left=arr.slice(0,mid);
                var right=arr.slice(mid);
                return merge(mergeSort(left),mergeSort(right))
            };
            console.log(mergeSort([25,18,17,31,25,30]))

控住台打印：

至此，我们的归并排序成功！
欢迎各位大小神同行予以指正和探讨