3 Way Merge Sort

3WayMergeSort.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
# Test cases to ensure that the 3-way Merge Sort is working correctly
assert mergeSort3([7,6,5,4,3,2,1])[0] == [1, 2, 3, 4, 5, 6, 7], "Not sorted Correctly"
assert mergeSort3([17,29,18,20,30,22,26,10,23,21])[0] == [10,17,18,20,21,22,23,26,29,30], "Not sorted Correctly"
assert mergeSort3([89,71,26,19,3,79,44,70,1,52,43,35,64,72,66,32,59,81,21,16,50,37,58,24,68,6,7,45,76,34])[0] == [1, 3, 6, 7, 16, 19, 21, 24, 26, 32, 34, 35, 37, 43, 44, 45, 50, 52, 58, 59, 64, 66, 68, 70, 71, 72, 76, 79, 81, 89], "Not sorted Correctly"
assert mergeSort3([1])[0] == [1], "Not sorted Correctly"
assert mergeSort3([2,1])[0] == [1,2], "Not sorted Correctly"
assert mergeSort3([1,2])[0] == [1,2], "Not sorted Correctly"
assert mergeSort3([3,2,1])[0] == [1,2,3], "Not sorted Correctly"
assert mergeSort3([1,2,3])[0] == [1,2,3], "Not sorted Correctly"
assert mergeSort3([1,3,2])[0] == [1,2,3], "Not sorted Correctly"
assert mergeSort3([3,1,2])[0] == [1,2,3], "Not sorted Correctly"