Python program to implement Merge Sort

# Merge Sort

import random
import math

c = 0 # Counter for Runtime Complexity
A = [] # List of elements
n = 0 # No. of elements

def getdata(): # Random Input
    for i in range(n):
        A.append(random.randint(0,n))

def showdata(): # Display all elements 
    for i in range(n):
        print(A[i],"\t",end="")
    print()

def merging(x,p,y):  # merges two sorted array
    global c
    i = x
    j = p+1
    k = x

    b = [0]*(x+y+1)
    while i<=p and j<=y:
        c=c+1
        if A[i] < A[j]:
            b[k]=A[i]
            i=i+1
        else:
            b[k]=A[j]
            j=j+1
        k=k+1

    while i<=p:
        c=c+1
        b[k]=A[i]
        k=k+1
        i=i+1

    while j<=y:
        c=c+1
        b[k]=A[j]
        k=k+1
        j=j+1

    for l in range(x, y+1):
        A[l]=b[l]


def merge_sort(x,y):
    global c
    if x<y:
        p = (x+y) // 2
        merge_sort(x,p)
        merge_sort(p+1,y)
        merging(x,p,y)


# __________________________ Main Block Starts __________________________
print("\t\t\t____Merge Sort____")
n = int(input("\nEnter number of elements: "))

getdata()
print("\nBefore Sorting: ")
showdata()
merge_sort(0, n-1)

print ("\nAfter Sorting: ")
showdata()

print("\nTheoretical Complexity : ", (n*math.log(n)))
print("Runtime Complexity: ", c)

Output