def merge_sort(values):
    if len(values) <= 1: return values[:]
    mid = len(values)//2
    left, right = merge_sort(values[:mid]), merge_sort(values[mid:])
    output=[]; i=j=0
    while i<len(left) and j<len(right):
        if left[i] <= right[j]: output.append(left[i]); i+=1
        else: output.append(right[j]); j+=1
    return output + left[i:] + right[j:]

assert merge_sort([7, 2, 9, 1, 4, 4]) == [1, 2, 4, 4, 7, 9]
print(merge_sort([7, 2, 9, 1, 4]))