lisp - 合并 2 个排序列表

Question

有人要求我针对以下问题提出尽可能多的解决方案:

Write a function which takes two lists of numbers (both assumed to be in ascending order) and merges them into a single list (also in ascending order).

我的第一个解决方案是将 append list1 到 list2 上，然后重新排序。

然后我发现了一个内置的merge。

然后我决定自己实际实现一个解决方案，我想出了一个尾递归函数，目前它只适用于列表的一个子集。

问题本身似乎也许我终于有理由阅读 Knuth，但可惜 Uni 和图书馆因下雪而关闭。

所以我求助于您，有什么有趣的、有效的或反模式的方法可以解决这个问题？

---

P.S 我不是在寻找实现，除非那是展示这个想法的最佳方式。我只是想看看人们是如何解决这类问题的。

Answer 1

合并两个排序列表在算法上是微不足道的。

从每个列表的第一个元素开始，比较，写入较低的元素以输出并在找到较低元素的列表中前进。继续前进，直到到达一个列表的末尾，然后放出另一个列表的剩余部分。

这只需要对每个列表和最大值进行一次循环。每个输出元素一个比较。

编辑:这对于两个列表来说是最有效的。当您有大量列表要合并时，它会变得(有点)棘手。