Assignment1

import random
import sys

sys.setrecursionlimit(10921)

integer = 3

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.append(output[0])
        left = output[1]
        middle = output[2]
        right = output[3]
        if len(left) == 0:
            array.append(merge_two(middle, right))
        elif len(middle) == 0:
            array.append(merge_two(left, right))
        elif len(right) == 0:
            array.append(merge_two(left, middle))
    elif len(left) == 0:
        array.append(merge_two(middle, right))
    elif len(middle) == 0:
        array.append(merge_two(left, right))
    elif len(right) == 0:
        array.append(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))
    
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))