Question

使用链表的时候归并排序和插入排序的区别是什么？

使用链表的时候归并排序和插入排序的区别是什么？
比如说9、1、2、3这个序列归并排序，先取9生成子序列A，然后再取1生成序列B，B和A按照归并操作的原理，A中的1进入序列C，然后把B复制到C后面，可是我感觉，这个和直接插到A后面没有区别啊。。。归并排序和插入排序区别是什么？

Answer 1

从本质上讲，所有的排序都没有区别，无外乎是“比较”、“移动”。
你所说的归并排序是“2-路归并排序”，初始得到4个有序序列：9、1、2、3；第一趟分别对9和1、2和3进行两两归并，得到1、9、2、3；第二趟对1、9和2、3两个有序子序列进行两两归并，得到1、2、3、9。
归并排序操作本质上还是先比较，再插入。它的时间复杂度是O(nlogn)。

你所说的插入排序是“直接插入排序”，初始得到1个有序序列：9；第一趟将1插入到初始有序序列中，得到1、9；第二趟将2插入到有序序列1、9中，得1、2、9；第三趟将3插入到有序序列1、2、9中，得到1、2、3、9。
直接插入操作本质是也是先比较，再插入。它的时间复杂度是O(n*n)。

如果一定要说两者的区别，归并排序是将一段有序记录插入到另一段有序记录中，插入排序是将一个记录插入到一段有序记录中。

Answer 2

长了就有区别了，比如1,3, 4和2,5,6,7,8，当你合并到1,2,3,4的时候5、6、7、8就直接复制后面了，你要插入排序插5从头开始比较一遍，插6再重头开始比较一遍……

归并排不稳定，没准比插排还慢，原来数列局部有序的话用归并就快