java - 合并排序 : Revision

Question

归并排序的工作方式是:

获取值列表

一分为二

取每个列表的第一个元素，最小值进入一个新列表(我想从原来的列表中删除)。比较接下来的两个数字 - 这样做直到一个列表为空，然后将另一个列表的其余部分放在 nw 列表的末尾？

此外，在链表上执行此操作的后果是什么？

谢谢

Answer 1

你描述的只是合并(没有排序)，排序是在归并排序中递归完成的。

Also, what are the ramifications of doing this on a linked list?

拆分链表的成本可能太高，如果您有两个已排序的列表，您可以轻松地合并它们以保持顺序。