Comparison between merge sort, insertion sort and 3 way merge sort. Augmented sort is the combination between insertion and merge sort to create the best time complexity

InsertionMergeSort.py

import time
import matplotlib.pyplot as plt
import random

def merge3(a,b,c):
    # Starting array that will be returned
    final = []
    # Starting pointers
    i=0 # pointer for array 'a'
    j=0 # pointer for array 'b'
    k=0 # pointer for array 'c'
    # While there is elements in all the lists
    while i < len(a) and j < len(b) and k < len(c):
        # Selecting what element to append first in the final list
        # based on their values
        # the pointers will increase by 1 unit when an element inside their
        # list is used
        if a[i] <= b[j] and a[i] <= c[k]:
            final.append(a[i])
            i+=1
        elif b[j] <= a[i] and b[j] <= c[k]:
            final.append(b[j])
            j+=1
        elif c[k] <= a[i] and c[k] <= b[j]:
            final.append(c[k])
            k+=1
    # In case one of the lists ends but we still have elements in 2 other lists
    # then our pointers for the remaining lists will continue to compare values and append on the final list accordingly
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            final.append(a[i])
            i+=1
        elif b[j] <= a[i]:
            final.append(b[j])
            j+=1

    while j < len(b) and k < len(c):
        if b[j] <= c[k]:
            final.append(b[j])
            j+=1
        elif c[k] <= b[j]:
            final.append(c[k])
            k+=1

    while i < len(a) and k < len(c):
        if a[i] <= c[k]:
            final.append(a[i])
            i+=1
        elif c[k] <= a[i]:
            final.append(c[k])
            k+=1
    # In case there is only 1 array remaining
    # since we can assume that the arrays are already sorted
    # we do not need to go element by element in the remaining array
    # we can just append the whole array in the end of the final because the
    # elements will already be sorted
    # No need to go element by element
    if i < len(a):
        final.extend(a[i:])

    if j < len(b):
        final.extend(b[j:])

    if k < len(c):
        final.extend(c[k:])
    # Returning the final sorted list
    return final

def merge2(a,b):
    #starting final array
    c = []
    #starting pointers
    j=0
    i=0
    # Pointers in 'a' and 'b' will compare their elements and append
    # the smallest one first in the final list
    while len(c) < (len(a)+len(b)):
        # if there is elements in both lists
        if i < len(b) and j < len(a):
            # choosing the lower element
            if a[j] >= b[i]:
                # appending on the final list
                c.append(b[i])
                # increasing pointer by 1 index
                i+=1
            elif a[j] <= b[i]:
                c.append(a[j])
                j+=1
        # in case we are done with one of the lists
        # we can just append the other one in the end of the final array
        # since we know that it will be sorted
        elif i == len(b):
            c.extend(a[j:])
        elif j == len(a):
            c.extend(b[i:])
    return c

def mergeSort3(array):
    start = time.time()
    # Returning the array itself if it has only 1 item
    if len(array) == 1:
        end = time.time()
        return array, end-start
    # Recalling this function if the array has only 2 items
    if len(array) ==2:
        hlef = array[:1]
        hrig = array[1:]
        # Calling this function to recursively obtain each individual item
        lef = mergeSort3(hlef)[0]
        rig = mergeSort3(hrig)[0]
        # Returning the sorted list
        end = time.time()
        return merge2(lef,rig), end-start
    # Splitting the array in different parts depending on its size
    if len(array)%3 !=0:
        if len(array)%3 ==1:
            h = (len(array)//3)
            
        elif len(array)%3 ==2:
            h = int(len(array)//3) + 1
    # If the array is divisible by 3 than our pointer 'h' will be the first third of the array
    else:
        h=int(len(array)/3)
    # Splitting the array in 3 depending on the value given to 'h'
    hlef = array[:h]
    hmid = array[h:2*h]
    hrig = array[2*h:]
    # Recursively splitting the array in 3 until we are done with the splits
    lef = mergeSort3(hlef)[0]
    mid = mergeSort3(hmid)[0]
    rig = mergeSort3(hrig)[0]
    # Returning the merged array
    end = time.time()
    return merge3(rig, mid, lef), end-start
  
def insertionSort(array):
    steps = 0
    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, end-start, steps)

def mergeInsertionSort(array):
    if len(array) < 110:
        return insertionSort(array)
    return mergeSort3(array)
  
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, sortAlgo):
    # Function to produce 2 arrays:
    # 1. Input size: array with the number of elements in a list
    # 2. Time Sort: Time 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
    timeSort = []
    inputSize=[]
    for a in range(starting,end,spaces):
        # Taking the number of steps for array of size specified accordingly to:
        # 'starting' 'end' 'spaces'
        timeSort.append(sortAlgo(creatingArray(a))[1])
        inputSize.append(a)
    # Output in the right format to be used in plt.plot
    return inputSize, timeSort

# Merge Sort vs Insertion Sort graph
graph = produceArray(1,1,200, mergeSort3)
plt.plot(graph[0], graph[1])
graph1 = produceArray(1,1,200, insertionSort)
plt.plot(graph1[0],graph1[1])
plt.legend(['Merge Sort', 'Insertion Sort'])
plt.title('Time X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Time in seconds')
plt.show()

# 3-way Merge Sort vs 2-way Merge Sort vs Augmented Merge Sort
graph = produceArray(1,1,500, mergeSort3)
plt.plot(graph[0], graph[1])
graph1 = produceArray(1,1,500, mergeSort2)
plt.plot(graph1[0],graph1[1])
graph1 = produceArray(1,1,500, mergeInsertionSort)
plt.plot(graph1[0],graph1[1])
plt.legend(['3-way Merge Sort', '2-way Merge Sort', 'Augmented Merge Sort'])
plt.title('Time X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Time in seconds')
plt.show()