В сортировке слиянием почему бы не объединить каждый отсортированный подсписок в скользящий список?

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) временной сложности.