# Recursive Python Program to Merge Three Sorted Lists

4324 views
1

Write a purely recursive Python function called `Merge3` that takes three lists of numbers each sorted in increasing order as input and outputs a single sorted list by merging elements from the three lists in proper increasing order. For example, `Merge3([1,2,72,108],[3,4,94,103],[45,67,456])` should return a list `[1,2,3,4,45,67,72,94,103,108,456]`.

I was able to write a version for two lists, but I'm struggling to come up with a compact way to do this for three lists. See my example below:

``````def Merge2(A, B):
if A == []:
return B
if B == []:
return A
if A != [] and B != []:
if A[0] > B[0]:
return [B[0]] + Merge(A, B[1:])
else:
return [A[0]] + Merge(A[1:], B)

print(Merge2([1, 2, 6, 7],[3, 4, 8, 9]))
``````

Is there an easy way to do this for three lists that I'm missing? I feel like it's going to require a lot of additional checking that will make the program fairly long. Can you come up with a concise way to do this for three lists?

If you can do it for two lists, technically speaking you've already done it for three lists. Since two lists return another sorted list you just apply your two list function twice -- first on A and B to get D, and then on D and C.

10

An easy way to solve this is to reuse `Merge2` that you already have:

``````def Merge3(A, B, C):
return Merge2(Merge2(A, B), C)
``````

posted this