InsertionSort vs MergeSort Time

'''
CHAPTER 1
'''

def insertionSort(A):
    n = len(A)
    for j in range(1, n):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
    return A

def Merge(A, p, q, r):
    n1 = q - p
    n2 = r - q + 1

    L = []
    R = []
    for i in range(0, n1):
        L.append(A[p + i])
    for j in range(0, n2):
        R.append(A[q + j])
    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1


def mergeSort(A, p, r):
    if p < r:
        q = (p + r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q + 1, r)
        Merge(A, p, q + 1, r)


import random
B = [random.randint(1, 200) for r in range(200)]

'''
CHAPTER 2
'''

from timeit import default_timer as timer
executions = list(range(20, 220, 20))
# executions = [20, 40, 60, .... , 180, 200]

measurements_insertionsort = []
measurements_mergesort = []
for s in executions:
    start = timer()
    insertionSort(B[0:s])
    end = timer()
    measurements_insertionsort.append(end - start)
    start = timer()
    mergeSort(B[0:s], 0, len(B[0:s]) - 1)
    end = timer()
    measurements_mergesort.append(end - start)

print("NumOfElements   InsertionSortTime(ms)      MergeSortTime(ms)")
for e, m1, m2 in zip(executions, measurements_insertionsort, measurements_mergesort):
    print(str(e) + "              " + str(1000 * m1) + "        " + str(1000 * m2))


'''
CHAPTER 3
'''

import matplotlib.pyplot as plt
plt.plot(executions, measurements_insertionsort, label="Insertion Sort")
plt.plot(executions, measurements_mergesort, label="Merge Sort")
plt.xlabel("Number of Elements")
plt.ylabel("Execution Time")
plt.legend()
plt.show()