Merge Sort

code: python

# O(nlogn), O(n)

def merge_sort(arr):

if len(arr) == 1:

return arr

mid = len(arr) // 2

left = merge_sort(left)

right = merge_sort(right)

return merge(left, right)

def merge(left, right):

result = []

i, j = 0, 0

while i < len(left) and j < len(right):

i += 1

else:

j += 1

return result

def test_heap_sort():