Code must be in python. Exercise 1 [10 pts]. As discussed in class, merge sort i
ID: 3718209 • Letter: C
Question
Code must be in python.
Exercise 1 [10 pts]. As discussed in class, merge sort is a recursive sorting algorithm that continually splits a list in half following the divide and conquer strategy. Once two halves are sorted, the fundamental operation "merge" is performed. Write the functions merge(listl, list2) [5 pts] and merge_sort(numList) [5 pts] to correctly sort a list of numbers. merge_sort is a recursive function that calls merge to return the final sorted list Remember: If the list is empty or has one item, it is sorted by definition Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list - EXAMPLES: >>>merge_sort ([12,35, 87,26,9,28,7]) 7, 9, 12, 26, 28, 35, 87 >>> merge ([12,26,35, 87, [7,9,28]) 7, 9, 12, 26, 28, 35, 87] >>> merge ([12,35], [26, 87]) 12, 26, 35, 871Explanation / Answer
# p is the index of left most element
# r is the index of right most element
def merge_sort_util(list1 , p , r):
if p < r:
# get the index of middle element
m = int( ( p + ( r - 1 ) ) / 2 )
# sort the left subarray
merge_sort_util(list1, p, m)
# sort the right subarray
merge_sort_util(list1, m + 1, r)
# merge the two subarrays
merge(list1, p, m, r)
# merge the two subarrays
def merge(list1, p, m, r):
len1 = m - p + 1
len2 = r - m
# create temporary array with each element 0
left = [0] * (len1)
right = [0] * (len2)
# Copy data to temp arrays left[] and right[]
for i in range(0 , len1):
left[i] = list1[p + i]
for j in range(0 , len2):
right[j] = list1[m + 1 + j]
i = 0
j = 0
k = p
while i < len1 and j < len2:
if left[i] <= right[j]:
list1[k] = left[i]
i += 1
else:
list1[k] = right[j]
j += 1
k += 1
# copy the remaining elements of left
while i < len1:
list1[k] = left[i]
i += 1
k += 1
# copy the remaining elements of right
while j < len2:
list1[k] = right[j]
j += 1
k += 1
def merge_sort( list1 ):
merge_sort_util( list1 , 0 , len(list1) - 1 )
return list1
print(merge_sort([12 , 35 , 87 , 26 , 9 , 28 , 7]))