合并 2 个排序列表

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

编写一个函数，它接受两个数字列表（均假设为 按升序排列）并将它们合并到一个列表中（也在 升序）。

我的第一个解决方案是append list1 onto list2然后重新sort.

然后我发现一个内置的merge.

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

问题本身似乎也许我终于有理由阅读高德纳了，但可惜大学和图书馆因下雪而关闭。

所以我问你，解决这个问题有哪些有趣的、有效的或反模式的方法？

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

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

从每个列表的第一个元素开始，进行比较，将较低的元素写入输出，然后将列表推进到找到较低元素的位置。继续下去，直到到达一个列表的末尾，然后列出另一个列表的其余部分。

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

编辑：这与两个列表一样有效。当您有大量列表需要合并时，它会变得（有点）棘手。