Recursive Python Program to Merge Three Sorted Lists

4324 views python

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:])
      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?

answered question

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.

1 Answer


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

Have an answer?


Please login first before posting an answer.