Assignment1Question1

#Question 1

import random

integer = 5

def random_list(integer):
    lst = []
    for x in range (integer):
        lst.append(random.randint(0, 100))
    return (lst)

def merge_two(left, right):
    array = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            array.append(left[0])
            left.pop(0)
        else:
            array.append(right[0])
            right.pop(0)
    while len(left) > 0:
        array.append(left[0])
        left.pop(0)
    while len(right) > 0:
        array.append(right[0])
        right.pop(0)
    return (array)
    
def merge_three(left, middle, right):
    array = []
    while len(left) > 0 and len(middle) > 0 and len(right) > 0:
        if left[0] <= middle[0] and left[0] <= right[0]:
            array.append(left[0])
            left.pop(0) 
        elif middle[0] <= left[0] and middle[0] <= right[0]:
            array.append(middle[0])
            middle.pop(0)
        elif right[0] <= left[0] and right[0] <= middle[0]:
            array.append(right[0])
            right.pop(0)
    return (array, left, middle, right)
    
def threeway_merge(left, middle, right):
    array = []
    if len(left) > 0 and len(middle) > 0 and len(right) > 0:
        output = merge_three(left, middle, right)
        array = array + output[0]
        left = output[1]
        middle = output[2]
        right = output[3]
        if len(left) == 0:
            array = array + merge_two(middle, right)
        elif len(middle) == 0:
            array = array + merge_two(left, right)
        elif len(right) == 0:
            array = array + merge_two(left, middle)
    elif len(left) == 0:
        array = array + merge_two(middle, right)
    elif len(middle) == 0:
        array = array + merge_two(left, right)
    elif len(right) == 0:
        array = array + merge_two(left, middle)
    return array
        
def threeway_mergesort(lst):
    if len(lst) <= 1:
        return lst
    else:
        left = lst[0:len(lst)//3]
        middle = lst[len(lst)//3:2*len(lst)//3]
        right = lst[2*len(lst)//3:len(lst)]
        left = threeway_mergesort(left)
        middle = threeway_mergesort(middle)
        right = threeway_mergesort(right)
    return (threeway_merge(left, middle, right))

random.seed(5)
    
lst1 = random_list(integer)
print (lst1)
print (threeway_mergesort(lst1))

lst2 = random_list(integer)
print (lst2)
print (threeway_mergesort(lst2))

lst3 = random_list(integer)
print (lst3)
print (threeway_mergesort(lst3))

#[62, 74, 80, 95, 74, 93, 2, 47, 95, 65]
#[2, 47, 62, 65, 74, 74, 80, 93, 95, 95]

#[90, 11, 47, 24, 54, 57, 1, 21, 28, 92]
#[1, 11, 21, 24, 28, 47, 54, 57, 90, 92]

#[77, 16, 80, 14, 62, 12, 0, 88, 21, 21]
#[0, 12, 14, 16, 21, 21, 62, 77, 80, 88]