def merge(l, r):
lp = rp = 0
result = []
while lp < len(l) and rp < len(r):
if l[lp] < r[rp]:
result.append(l[lp])
lp += 1
else:
result.append(r[rp])
rp += 1
while lp < len(l):
result.append(l[lp])
lp += 1
while rp < len(r):
result.append(r[rp])
rp += 1
return result
def mergeSort(lst):
if len(lst) <= 1:
return lst
midIdx = len(lst) // 2
l = mergeSort(lst[:midIdx])
r = mergeSort(lst[midIdx:])
return merge(l, r)
print(mergeSort([1, 5, 4, 8, 9, 3, 7, 6, 2])) # => [1, 2, 3, 4, 5, 6, 7, 8, 9]