在合并排序中，为什么不将每个排序的子列表合并到滚动列表中?

Question

所以对于拆分时的合并排序，我会有

HGFEDCBA
HG FE DC BA
H G F E D C B A

用于合并而不是

GH EF DC AB
EFGH  ABCD
ABCDEFGH

为什么不呢

H G F E D C B A
GH F E D C B A
FGH E D C B A
EFGH D C B A
DEFGH C B A
CDEFGH B A
CBDEFGH A
ABCDEFGH 

我唯一能想到的是，合并排序通常是递归实现的，如果使用递归拆分，则使用第一种方法更容易合并。

Answer 1

正如一些评论所提到的，您的第二张图片实际上是描述插入排序而不是合并排序。我理解您的困惑，因为在您的示例中，插入排序会比合并排序运行得更快。反向列表的插入排序为 O(n(，因为添加到输出数组的每个新元素在插入之前只需要比较一个元素。但是，合并排序在所有情况下都需要 O(n logn( 比较。

但是您说合并排序比一般插入排序的比较少是正确的。例如，如果列表已经排序("ABCDEFGH"(，则添加到输出中的每个新元素都必须在添加到末尾之前将其自身与整个输出进行比较，这将是 O(n^2( 时间复杂度。