merge sort function
def merge_sort(arr):
"""Execute the merge sort algorithm"""
if len(arr) > 1:
# recursive case
mid = len(arr) // 2 # find the midpoint of the array
l = arr[:mid] # define the left half of the array
r = arr[mid:] # define the right half of the array
l = merge_sort(l) # sort the left half by calling this function
r = merge_sort(r) # sort the right half by calling this function
# now merge the two lists
merged = [] # define an empty merged array
while len(l) > 0 and len(r) > 0:
# compare the heads of the left and right array
if l[0] <= r[0]:
# if the head of the left list is smaller than the head of the right list
# pop the head of the left list and append it to the merged list
merged.append(l.pop(0))
else:
# otherwise, pop the head of the right list and append that
merged.append(r.pop(0))
# add any elements remaining in the left or right list to the merged list
merged = merged + l + r
return merged
else:
# base case
return arr