关于javascript:javascript数据结构与算法归并排序

归并排序采纳了分治策略，在对数组进行排序的时候，先将数组宰割成更小的子数组，而后对子数组排序，最初排序后的子数组合并成一个实现的数组，在对子数组排序的时候能够应用雷同的策略持续对子数组进行宰割，直到子数组中只蕴含一个元素。
例如咱们须要数组 [3,2,6,4,8,1,7,5] 排序，首先将数组宰割成只蕴含单个元素的子数组:

[3] [2]  [6] [4]  [8]  [1]  [7]  [5]

将相邻的两个子数组合并，失去蕴含两个元素的已排序子数组：

[2, 3]   [4, 6]  [1, 8]  [5, 7]

持续两两合并：

[2, 3, 4, 6]  [1, 5, 7, 8]

最终就能够失去一个实现的排序好的数组了：

[1, 2, 3, 4, 5, 6, 7, 8]

上面看一下怎么用 JS 代码实现一个归并排序。
首先看一下怎么合并两个已排序的子数组，代码如下：

/**
 * 辅助办法，合并数组 arr 中的两个已排序的子数组
 * 作为例子只思考从小到大排序，其余排序可自定义比拟函数，相似于 Array#sort
 * @param {*} arr 数组
 * @param {*} start 起始地位
 * @param {*} end 完结地位（蕴含在范畴内）* @param {*} mid 两个子数组的宰割地位
 */
function merge(arr, start, end, mid) {
 // 须要合并的元素个数
 const count = end - start + 1;
 // 左侧已排序数组
 const left = arr.slice(start, mid + 1);
 // 右侧已排序数组
 const right = arr.slice(mid + 1, end + 1);
 // 退出守卫元素，这样能够不必判断子数组是否为空
 left.push(Infinity);
 right.push(Infinity);
 // 顺次取出两个子数组中的较小的值
 let i = 0;
 let l = 0;
 let r = 0;
 while(i < count) {if (left[l] < right[r]) {arr[start + i] = left[l];
 l++;
 } else {arr[start + i] = right[r];
 r++;
 }
 i++;
 }
}

能够把两个已排序的子数组看作是两堆扑克，每次从两队扑克中取出较小的一张牌，直到所有的牌取完，失去的就是一副排好序的扑克。

上面看一下如何应用递归实现归并排序：

首先计算出中心点将数组宰割成两个子数组，对两个子数组别离排序，最初调用 merge 函数将两个已排序的子数组合并失去最终的排序数组。