本文转载自微信公众号《JS日报》，作者灰灰。转载本文请联系JS每日一问公众号.一、什么是归并排序（MergeSort）是一种建立归并操作的有效且稳定的排序算法。该算法是分治法的一个非常典型的应用，将有序的子序列合并，得到一个完整的有机序列。有序序列，即先让每个子序列有序，再让子序列有序长度为1）然后两两合并，使n个有序列表变成n/2个长度为2或1的有序列表（例如，4个小的有序列表合并成2个大的有序列表）通过不断进行两两合并，直到得到一个长度为n的有序列表。例如对无序列表{49,38,65,97,76,13,27}进行合并排序分为拆分和合并两部分：如下图所示：在合并的过程中，新的子-每次得到的表都是有序的，所以最终的有序表分为两部分，称为双向合并，如果分为三部分，则称为三向合并，以此类推2。归并排序算法的实现方法如下：划分：将数组分成两半，然后递归划分子数组，直到达到每个单独的数字。Combine：将两个数组合成一个有序数组，然后合并有序数组，直到所有的子数组组合成一个完整的数组。合并操作可以创建一个新数组来存储排序后的数组。比较两个有序数组的头部。较小的一个出列并推入其中。如果上面两个数组中还有值，重复上面的第二步。如果只有一个数组有值，则将数组的值出队并将其推入新创建的数组。代码表示如下所示：functionmergeSort(arr){//采用自上而下的递归方法constlen=arr.length;if(len<2){returnarr;}letmiddle=Math.floor(len/2),left=arr.slice(0,middle),right=arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left,right){constresult=[];while(left.length&&right.长度){如果(左[0]<=右[0]){result.push(left.shift());}else{result.push(right.shift());}}while(left.length)result.push(left.shift());while(right.length)result.push(right.shift());returnresult;}上面的合并分为两部分：划分和合并。在处理除法的过程中，递归调用了两次除法运算，耗时为2倍T(n/2)，合并运算的时间复杂度为O(n)，所以有如下公式可以得到：总执行时间=2×输入长度为n/2的sort函数执行时间+merge函数执行时间O(n)只有一个元素时，T(1)=O(1)如果T(n)=2*T(n/2)+O(n)左右/n操作，得到T(n)/n=(n/2)*T(n/2)+O(1)现在令S(n)=T(n)/n，则S(1)=O(1)，然后用表达式得到S(n)=S(n/2)+O(1)所以你可以得到：S(n)=S(n/2)+O(1)=S(n/4)+O(2)=S(n/8)+O(3)=S(n/2^k)+O(k)=S(1)+O(logn)=O(logn)综上所述，T(n)=n*log(n)=nlogn关于归并排序的稳定性，在这个过程中合并，当有1个或2个元素时，1个元素不会交换，如果两个元素大小相等，则不会交换。可见归并排序是一种稳定的排序算法。3、应用场景通常在外排序使用sort-merge策略，外排序指的是对超出内存限制的数据进行处理的排序算法。通常，中间结果放在读写速度较慢的外部存储器中。分为两个阶段如下：排序阶段：读取并放入内存中的数据量，排序输出到临时文件，一次一个，将排序后的数据组织成多个有序的临时文件合并阶段：合并这些临时文件变成大的有序文件例如用100m内存对900m数据进行排序，过程如下：读入100m数据内存，按照常规方式对排序后的数据进行排序，将排序后的数据写入磁盘，重复前两步，得到9个100m的临时文件。将100m的内存分成10份，将第9份作为输入缓冲区，第10份作为输出缓冲区进行九路归并排序，结果输出到缓冲区。如果输出缓冲器当该区域已满时，将数据写入目标文件并清除缓冲区。如果缓冲区为空，则读取对应文件的下一条数据。参考https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015https://chowdera.com/2021/09/20210920201630258d.html#_127https://juejin.cn/post/6844904007899561998
