How to define a recursive function to merge two sorted lists and return a new list with a increasing order in Python?

Question

I want to define a recursive function to merge two sorted lists (these two lists are sorted) and return a new list containing all the values in both argument lists with a increasing order. I know I can use list.extend() and sorted() to get that,but I don't want to use them. I just want to do some exercise about the recursion.

For example:

if a = [1,2,3,4], b = [5,6,7,8]

print(function(a,b))

[1,2,3,4,5,6,7,8]

This is my code:

def combine(a:list, b:list):    
    alist = []
    if a == [] and b == []:
       return alist
    if a != [] and b == []:
       return alist + a
    if a == [] and b != []:
       return alist + b     
    if a != [] and b != []:
       if a[0] <= b[0]:
          alist.append(a[0])
          return combine(a[1:], b)
       if a[0] > b[0]:
          alist.append(b[0])
          return combine(a, b[1:])
    return alist

I always get [5,6,7,8]. How should I do to get [1,2,3,4,5,6,7,8]?

Answer 1

Just a simpler version:

def combine(a, b):
    if a and b:
        if a[0] > b[0]:
            a, b = b, a
        return [a[0]] + combine(a[1:], b)
    return a + b

Test:

>>> combine([1,3,6,8], [2,4,5,7])
[1, 2, 3, 4, 5, 6, 7, 8]