#
from timeit import timeit
from random import randint

def merge(list1, list2):  #  assumption here is list 1 and list 2 is sorted
    list_sorted = []  # an empty list to add the sorted items
    while list1 !=[] and list2 != []: # keep looping while bot lists are not empty
        if list1[0] < list2[0]: # checking is list1 is the smallest if it is
            list_sorted.append(list1.pop(0)) # append it to list sorted and remove it
        else:
            list_sorted.append(list2.pop(0)) # if not smallest item is in list 2 to add that to the sorted list and remove it
    if len(list1)<1:  # while loop breaks if one list is empty, if it list1
        list_sorted += list2 # add list2 to the sorted list
    else:
        list_sorted += list1 # else it means list1 has data so that has to be added to the sorted list
    return list_sorted  ##could we use list 2 instead??
    
a = [2,5,7,9,12,45,234,1900]
b = [1,4,6,8,9]
# [1, 2, 4, 5, 6, 7, 8, 9, 9, 12, 45, 234, 1900]

#print(merge(a,b))

def merge_sort(unsorted):
    #print(unsorted)
    if len(unsorted) <=1: #  has the list got 1 or less than one elements
        return unsorted # it's sorted
    else:
        middle = int(len(unsorted) / 2) # rounds down if odd number
        front = merge_sort(unsorted[:middle]) # split out the front part)
        back = merge_sort(unsorted[middle:]) # and no the back part
        #print(front, back)
    return merge(front, back)
    
def bubblesort(unsorted):
    my_sorted_list = unsorted[:]
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(my_sorted_list)-1):
            if my_sorted_list[i] > my_sorted_list[i+1]:
                my_sorted_list[i], my_sorted_list[i+1] = my_sorted_list[i +1], my_sorted_list[i]
                swapped = True
        #print(my_sorted_list)

#c=[20, 15,6,4,20]
#Generate a large (1000 items) random list 
list_to_sort = ([randint(0,100000) for i in range(10)])

# list_to_sort = [2674, 3120, 5911, 8147, 9192, 9702, 9714, 11511, 11572, 12092, 13451, 13453, 15418, 16565, 17627, 17785, 18858, 19049, 21750, 22668, 24164, 26367, 26486, 27013, 27182, 27479, 29819, 31372, 31611, 33560, 33968, 34125, 34496, 35104, 36569, 38053, 38669, 40038, 40498, 40598, 40955, 41011, 41608, 42607, 43306, 44277, 44454, 44674, 45246, 46185, 48490, 49361, 51108, 52358, 53998, 55862, 56081, 56590, 58293, 59160, 61034, 61094, 61348, 61458, 61955, 62512, 63155, 63320, 64268, 66897, 67455, 68039, 69213, 69970, 71596, 74814, 75375, 75495, 75806, 78562, 80422, 80909,  85979, 89025,83456, 85166, 89038, 90272, 90885, 91317, 92006, 93843, 94069, 96714, 97328, 96261, 96697,  97404, 98384, 99061]

#Create anonymous functions to use with timeit, be sure to check these function names match your pasted ones
bs = lambda: bubblesort(list_to_sort)
ms = lambda: merge_sort(list_to_sort)
ts = lambda: sorted(list_to_sort)

#print(merge_sort(c))

#time the functions for 100 runs each
print("Merge took:")
print(timeit(ms, number = 100))

print("Bubble took:")
print(timeit(bs, number = 100))

print("Timsort took:")
print(timeit(ts, number = 100))