def merge_sort(x):
    """
    Merge sort, not super memory efficient
    """

    # a list of length 0 or 1 is already sorted
    if len(x) < 2:
        return x

    # split in half
    p = len(x)//2

    # sort the halfs
    l, r = merge_sort(x[:p]), merge_sort(x[p:])

    # merge the sorted halfs
    i = j = 0
    result = []
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(r[j])
            j += 1

    return result + l[i:] + r[j:]