from timeit import timeit
from random import randint

##################################################################
# COPY AND PASTE YOUR bubble_sort AND merge_sort functions below #
##################################################################


def merge(list_a, list_b):
    list_c = []
    while len(list_a) > 0  and len(list_b) > 0:
        if list_a[0] < list_b[0]:
            list_c.append(list_a.pop(0))
        else:
            list_c.append(list_b.pop(0))
    if list_a == []:
        list_c += list_b
    else:
        list_c += list_a
#   print("merged list is", list_c)
    return list_c


def merge_sort(unsorted):
    if len(unsorted) < 2:
        return unsorted
    else:
        middle = len(unsorted) // 2
        front = unsorted[:middle]
        back = unsorted[middle:]
#       print("splits are", front, back)
        front = merge_sort(front)
        back = merge_sort(back)
    return merge(front, back)


def bubble_sort(unsorted):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(unsorted)-1):
            if unsorted[i] > unsorted[i+1]:
                temp=unsorted[i]
                unsorted[i]=unsorted[i+1]
                unsorted[i+1]=temp
                swapped = True
    return unsorted

#Generate a large (1000 items) random list
for i in range(10):
    list_to_sort = [randint(0,100000) for i in range(50000)]
    #list_to_sort=[]
    #for i in range(50):
        #list_to_sort.append(50)

    unsorted = list_to_sort[:]
    #print("Buble list = ", list_to_sort)

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

    #time the functions for 100 runs each
    merge_var=timeit(ms, number = 100)
    print("Merge took: ",merge_var)
    bubble_var=timeit(bs, number = 100)
    print("Bubble took: ",bubble_var)
    ts_var=timeit(ts, number = 100)
    print("TimSort took: ",ts_var)
    #if merge_var<bubble_var:
        #print("Merge is better ")
    #else:
        #print("Bubble better")