merge_sort.py

#!/usr/bin/env python

importrandom
fromtypingimportList


defmerge_sort(arr: List[int]) ->List[int]:
iflen(arr) <=1:
returnarr
mid=len(arr) //2
left=merge_sort(arr[:mid])
right=merge_sort(arr[mid:])
returnmerge(left, right)


defmerge(left: List[int], right: List[int]) ->List[int]:
merged= []
i=j=0
whilei<len(left) andj<len(right):
ifleft[i] <=right[j]:
merged.append(left[i])
i+=1
else:
merged.append(right[j])
j+=1
merged.extend(left[i:])
merged.extend(right[j:])
returnmerged


defgenerate_random_list(size: int=10, lower: int=1, upper: int=100) ->List[int]:
return [random.randint(lower, upper) for_inrange(size)]


defmain():
"""
 Executes the merge sort algorithm with a randomly generated list.
 Time Complexity: O(n log n)
 """
rand_num_li=generate_random_list()
print(f"Unsorted List: {rand_num_li}")
sorted_list=merge_sort(rand_num_li)
print(f"Sorted List: {sorted_list}")


if__name__=='__main__':
main()