Please Complete the following code to plot the required graphs in python. Read the details below.

Consider the Mergesort and Insertion Sorting Algorithms. Implement these algorithms in Python. Given an input n each code should return the number of comparisons (nc) performed. Run the codes for three dierent cases: a sorted array, a reversed array and a randomly created array. Run the Insert and Mergesort codes for n = 10, 30, 100, 300, 103, 3103, 104, 105. Create two plots using a graphing tool you have used. The rst plot should show the results of Insertion Sort and Mergesort using a loglog scale (on the x-axis log(n), on the y-axis log(nc)). You can verify the theoretical behaviour of Insertion Sort and Mergesort from this plot. The second plot should show the results of Mergesort using log scale on the x-axis only. The y-axis should show the values of nc/n.Again show the curves for random, sorted and reversed inputs that you create as described above. In both plots, explain the shape of the graphs you observe.

Insertion sort code

def insertion_sort(a):

"""insertion_sort(a) -- sorts a by insertion sort

Returns number of comparisons"""

n_comparisons = 0

for i in range(1,len(a)):

j = i-1

n_comparisons = n_comparisons + 1

while a[j] > a[j+1]:

n_comparisons = n_comparisons + 1

# swap a[j] and a[j+1]

temp = a[j]

a[j] = a[j+1]

a[j+1] = temp

j = j-1

if j < 0:

break

return n_comparisons

if __name__ == '__main__':

a = [3,8,2,0,1,6,5,8,4,12,7,9]

a_old = a.copy()

print('Number of comparisons =',insertion_sort(a))

print('a =',a_old)

print('sorted a =',a)

------------------------------------------------------------------------------------------------

def mergesort1(a):

"""mergesort1(a) -- returns sorted list of a's elements

Uses mergesort algorithm applied to lists using append

Returns pair of sorted list and number of comparisions"""

n = len(a)

if n <= 1:

return a,0

else:

m = n // 2

a1 = a[0:m]

a2 = a[m:n]

b1,nc1 = mergesort1(a1)

b2,nc2 = mergesort1(a2)

b, nc3 = merge1(b1,b2)

return b,(nc1+nc2+nc3)

def merge1(l1,l2):

"""merge1(l1,l2) -- returns merged list containing entries of lists l1

& l2

Returns pair of the merged list and the number of comparisons between

items"""

l = []

n1 = len(l1)

n2 = len(l2)

i1 = 0

i2 = 0

n_comparisons = 0

while i1 < n1 and i2 < n2:

n_comparisons = n_comparisons + 1

if l1[i1] <= l2[i2]:

l.append(l1[i1])

i1 = i1 + 1

else:

l.append(l2[i2])

i2 = i2 + 1

while i1 < n1:

l.append(l1[i1])

i1 = i1 + 1

while i2 < n2:

l.append(l2[i2])

i2 = i2 + 1

return l,n_comparisons

if __name__ == '__main__':

a = [3,8,2,0,1,6,5,8,4,12,7,9]

a_old = a.copy()

a,nc = mergesort1(a)

print('Number of comparisons =',nc)

print('a =',a_old)

print('sorted a =',a)

------------------------------------------------------------------------------------------------------------

import matplotlib.pyplot as plt

import math

def FirstPlot(x,y,c):

logx = []

logy = []

for i in x:

logx.append(math.log10(i))

for i in y:

logy.append(math.log10(i))

print('Plotting now!')

plt.plot(logx,logy,label=c)

plt.legend()

print('Done plotting!')

if __name__=='__main__':

#First Plot

plt.figure("First Plot")

nlist = [10,30,100,300]

nc_sorted_MergeSort = [30,258,2538,23386]

FirstPlot(nlist,nc_sorted_MergeSort,'Sorted Array-MergeSort')

plt.show()

print('done')