Merging two ordered lists

merge-without-slice.py

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

    last = y.pop() if x[-1] < y[-1] else x.pop()
    # 'merged' is required because the append method is in place
    merged = merge(x, y)
    merged.append(last)
    return merged

merge.py

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

O problema é que se estamos falando de listas do python, slice e concat custam O(n), o que faz com que seu algoritmo seja O(n^2), que perde todo o sentido.

Adicionei uma solução sem slice e concat.