MergeSort.py

import time
import matplotlib.pyplot as plt
import random

def merge(a,b,steps):
    # creating array
    c = []
    # creating pointers
    j=0
    i=0
    # only stops when our newly created array has the same number of elements
    # as the 2 arrays that we started with.
    while len(c) < (len(a)+len(b)):
        #comparing pointers of each array and adding to the third one 'c'
        # in order to make the third one sorted
        if i < len(b) and j < len(a):
            if a[j] > b[i]:
                steps+=1
                c.append(b[i])
                i+=1
            elif a[j] < b[i]:
                steps+=1
                c.append(a[j])
                j+=1
        elif i == len(b):
            steps+=1
            c.append(a[j])
            j+=1
        elif j == len(a):
            steps+=1
            c.append(b[i])
            i+=1
    return c, steps

#print(merge([1,4,6,7,9],[2,3,5,8,10]))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# it is merging correctly 2 arrays

def Mergesort(array, steps):
    steps+=1
    # checking if the array is already broken enough or not
    if len(array) > 1:
        # getting to the middle of the array
        if len(array)%2 !=0:
            h = int((len(array)+1)/2)
        else:
            h=int(len(array)/2)
        #getting the left and right side
        hlef = array[:h]
        hrig = array[h:]
        #splitting the left and right side
        lef = Mergesort(hlef, steps)
        rig = Mergesort(hrig, steps)
        # merging both sides if they are not empty
        if lef[0] or rig[0] !=None:
            #print(steps)
            steps+=1
            helper = merge(rig[0], lef[0],steps)
            array = helper[0]
            steps+=helper[1]
        # returning the merged array
        return array, steps
    # we return the array itself when it uses only 1 element because we do not
    # need to split it again
    else:
        return array, steps

def creatingArray(n):
    # Function to create a non-sorted array of size 'n'
    array = []
    # creating a list of range specified by the first argument in the function
    for a in range(n):
        array.append(a)
    # Now we are going to make the 'n' size divided by 2 swaps
    # so the array is not sorted correctly
    for _ in range(int(len(array)/2)):
        i1, i2 = random.sample(array, 2)
        array[i1], array[i2] = array[i2], array[i1]
    # returning an unsorted array of the size that was specified
    return array

def produceArray(starting, spaces, end, sort):
    # Function to produce 2 arrays:
    # 1. Input size: array with the number of elements in a list
    # 2. Steps Sort: number of steps it took to process the input size
    # It takes 4 arguments:
    # starting: Starting Input size
    # spaces: how many input sizes it 'jumps' after considering each input size
    # end: ending Input size
    # sort: sorting algorithm
    stepsSort = []
    inputSize=[]
    for a in range(starting,end,spaces):
        # Taking the number of steps for array of size specified accordingly to:
        # 'starting' 'end' 'spaces'
        stepsSort.append(sort(creatingArray(a), 0)[1])
        inputSize.append(a)
    # Output in the right format to be used in plt.plot
    return inputSize, stepsSort

#print(Mergesort([9,8,7,6,5,4,3,2,1], 0))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
# It is sorting correctly

# Insertion Sort function that counts the number of steps
def insertionSort(array, steps):
    start = time.time()
    for a in range(1,len(array)):
        steps+=1
        key = array[a]
        b = a-1
        while b>=0 and array[b]>key:
            steps+=1
            array[b+1]=array[b]
            b-=1
        steps+=1
        array[b+1]=key
    end = time.time()
    return (array, steps)

# Doing the graphs to compare the sorting algorithms and their number of steps

# producing arrays with input sizes and the respective number of steps
# that it took to sort using the given sorting algorithm
graph = produceArray(1,100,2000, Mergesort)
plt.plot(graph[0], graph[1])
graph1 = produceArray(1,100,2000, insertionSort)
plt.plot(graph1[0],graph1[1])
plt.legend(['Merge Sort', 'Insertion Sort'])
plt.title('Steps X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Steps')
plt.show()


graph = produceArray(1,10,100, Mergesort)
plt.plot(graph[0], graph[1])
graph1 = produceArray(1,10,100, insertionSort)
plt.plot(graph1[0],graph1[1])
plt.legend(['Merge Sort', 'Insertion Sort'])
plt.title('Steps X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Steps')
plt.show()

graph = produceArray(1,100,5000, Mergesort)
plt.plot(graph[0], graph[1])
plt.title('Steps X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Steps')
plt.show()

Comparing Mergesort with Insertion sort in the number of steps it takes for both to complete:

Mergesort number of steps (its around the input size):