Mergesort是一种基于合并操作的有效，稳定的分类算法。该算法是划分和征服的非常典型的应用。
合并和分类的主要思想是分割法律。主要过程是：
1.将n个元素从中间切成两个部分，分为两部分。
2.其余数组被递归划分，直到数组的大小为1。此时，只有一个元素，因此数组是有序的。
3.逐渐将两行序列从底层合并。将1的两个阵列置于有序的列中，大小为2，然后将两个尺寸合并为2个排序列，为有序的序列4 ...直到所有小的小阵列合并。
那么如何合成两个有序的列？
让我们抬起栗子手柄，一眼就能理解。
例如，有阵列arr [3,7,8,10,2,4,6,9];我们可以将这个数字分为两个有序的后续序列。
[3、7、8、10]和[2、4、6、9]合并为有序的序列[2,3,4,6,7,8,9,10]。
第一步：
拆除这两个小阵列中的左数组和右数组。如下图所示，使用了左侧的第一个元素，并且使用j的第一个元素到右。
第2步：
建立一个空气阵列ARR并使用K指向数组的第一个元素。
第三步：
与i和j指向的数字相比，小数字同时放置在k的位置，将小数的位置和k的位置移动到右侧。
2 < 3 , 将 2 填入 arr 数组 ，同时右移 j 和 k。
3 < 4 , 将 3 填入 arr 数组 ，同时右移 i 和 k。
4 < 7，将 4 填入arr 数组，同时右移 j 和 k。
6 < 7，将 6 填入arr 数组，同时右移 j 和 k。
7 < 9，将 7 填入arr 数组，同时右移 i 和 k。
8 < 9，将 8 填入arr 数组，同时右移 i 和 k。
10 > 9.填充ARR阵列并同时移动J和K。
可以发现右数组目前已经完成，因此目前，您只需要填写左侧数组中剩余的数字中的剩余数字。
猛烈的操作就像一只老虎一样，因此两个有序的阵列通过合并以良好的顺序排列。很好吗？
因此，问题是，您只能在合并和分类中安排这样的有序数组吗？
如果有一个无序的数组，该怎么办？
目前，分裂策略（分裂）成一些小问题（分裂）成一些小问题，然后递归，而分裂阶段的阶段“修复”在一起，将其分开）。
实际上，以上的第三部分是规则的过程，将两个有序序列结合到有序的序列中。
Little Chestnut：图形的无序序列由Hill执行。
输出：
时间复杂性：o（nlogn）。
空间复杂性：O（n），合并和排序需要与原始数组相同的长度来帮助排序。
稳定性：稳定性，因为在切换元素时，您可以在平等情况下对非动力进行限制，因此合并和排序可以稳定。
合并排序需要与要排序的数组相同的空间的临时数组。因此，您需要考虑使用合并和排序时是否存在空间限制。没有空间限制，合并和排序是一个不错的选择。
本文分享了华为云社区的诚意，作者：Bigsai。