merge.py

split_list = lambda x: (x[:len(x) // 2], x[len(x) // 2:])

def merge_lists(x, y):
    merged = []
    while len(x) > 0 and len(y) > 0:
        if x[0] <= y[0]:
            merged.append(x[0])
            x = x[1:]
        else:
            merged.append(y[0])
            y = y[1:]
    merged += x or y
    return merged

sort_pair = lambda x: x[:] if x[0] <= x[1] else x[::-1]

def sort_list(x):
    if len(x) <= 1:
        return x[:]
    elif len(x) == 2:
        return sort_pair(x)
    else:
        left, right = split_list(x)
        left = sort_list(left)
        right = sort_list(right)
        return merge_lists(left, right)


from random import shuffle
sample = list(range(50))
shuffle(sample)
print(sample)
print(sort_list(sample))