合并排序和插入排序的区别

合并排序： 是一种外部算法，基于分而治之的策略。在这个排序中：

• 元素被一次又一次地分成两个子数组(n/2)，直到只剩下一个元素。
• 合并排序使用额外的存储空间对辅助数组进行排序。
• 合并排序使用三个数组，其中两个用于存储每一半，第三个外部用于通过合并另外两个来存储最终排序列表，然后每个数组递归排序。
• 最后，合并所有子数组，使其成为数组的“n”个元素大小。

下面是说明合并排序的图像：

插入排序 是一种排序算法，其中从未排序的项目中取出元素，将其按排序顺序插入其他项目的前面，并重复直到所有项目都按顺序排列。该算法实现起来很简单，通常由两个循环组成：一个用于挑选项目的外循环和一个用于遍历数组的内循环。它的工作原理是对我们手中的扑克牌进行分类。

下面是说明插入排序的图像：

合并排序和插入排序的区别：

时间复杂度： 在合并排序中，最坏情况： O(N*log N) ，平均情况： O(N*log N) ，最佳情况： O(N*log N)

在插入排序中，最坏情况：O(N2)，平均情况：O(N2)，最佳情况：O(N)。

空间复杂度： 合并排序是递归的，占用了 O(N) 的辅助空间复杂度，因此它不能优于内存问题的地方。

在插入排序中仅需要 O(1) 辅助空间复杂度。它只使用一个额外的变量对整个数组进行排序。

数据集： 合并排序是大型数据集的首选。它碰巧比较了数组中存在的所有元素，因此对小型数据集没有太大帮助。

对于较少的元素，插入排序是首选。当数据已经排序或几乎排序时，它会变得很快，因为它会跳过排序的值。

效率： 考虑到这两种算法的平均时间复杂度，我们可以说合并排序在时间方面是有效的，而插入排序在空间方面是有效的。

排序方法： 归并排序是一种外部排序方法，其中待排序的数据在内存中无法容纳，需要辅助内存进行排序。

插入排序基于这样一种思想，即在每次迭代中消耗输入元素中的一个元素以找到其正确位置，即它在排序数组中所属的位置。

稳定性： 合并排序是稳定的，因为具有相等值的两个元素在排序输出中出现的顺序与它们在输入未排序数组中的顺序相同，

插入排序在两种数据结构(数组和链表)上都需要 O(N2) 时间。如果 CPU 具有高效的内存块移动功能，那么阵列可能会更快。否则，可能没有那么大的时差。

合并排序和插入排序的区别：