Merge sort using two recursive functions rather than one recursive and one iterative

Question

I've tried to use divide and conquer to create a merge sort algorithm. It is made up of a mergesort recursive function which I'm confident is correct but within it it calls a merge function, which is also recursive but isn't working. So I was wondering if anyone could help me fix this so that it works. I've seen the other solutions for defining merge using while loops etc and I get the idea there but I want to see if the merge function can be written recursively instead.

At the moment the when I implement the code I just get an empty array which is frustrating.

def mergesort(A):
    length_A = len(A)
    if length_A > 1:
        return merge(
            mergesort(A[0:length_A//2]),
            mergesort(A[length_A//2 + 1:length_A-1]))
    else:
        return A

def merge(x,y):
    length_x = len(x)
    length_y = len(y)
    if length_x == 0:
        return x
    if length_y == 0:
        return y

    if x[0] <= y[0]:
        return x[0] + merge(x[1:length_x -1],y[0:length_y -1])
    else:
        return y[0] + merge(x[0:length_x-1],y[1:length_y -1])

A = [10, 2, 5, 3, 7, 13, 1, 6]
a = mergesort(A)
print(a)

Answer 1

Two things:

In the merge, if one of the lists to be merged is empty, you don't want to return that list, you want to return the other because this is the one with the remaining values. In other words, this is backward:

if length_x == 0:
    return x

if length_y == 0:
    return y

It should be:

if length_x == 0:
    return y

if length_y == 0:
    return x

Also you are trying to concat ints and lists with this:

# x[0] is a number
return x[0] + merge(x[1:length_x -1],y[0:length_y -1])

Something like this might be a little better:

def mergesort(A):
    length_A = len(A)
    split = length_A // 2

    if length_A > 1:
        return merge(mergesort(A[0:split]), mergesort(A[split:]))
    else:
        return A


def merge(x,y):
    if len(x) == 0:
        return y

    if len(y) == 0:
        return x

    if x[0] <= y[0]:
        return [x[0]] + merge(x[1:], y)
    else:
        return [y[0]] + merge(x, y[1:])


A = [10,2,5,3,7,13,1,6]
a = mergesort(A)
print(a)

result

[1, 2, 3, 5, 6, 7, 10, 13]