# compare timing of bubble, merge, and built-in sort
from timeit import timeit
from random import randint

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

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) <= 1:
        return unsorted
    else:
        middle = len(unsorted) // 2
        front = unsorted[:middle]
        back = unsorted[middle:]
    return merge(front, back)

def tim_sort(unsorted):
    return sorted(unsorted)

#Generate a random list
list_to_sort = [randint(0,10000) for i in range(500)]

tiny_list = [randint(0,10000) for i in range(10)]

ordered_list = sorted(list_to_sort)

def nearly_ordered(list_to_sort):
    ordered_list = sorted(list_to_sort)
    ordered_list.append(ordered_list.pop(5))
    return ordered_list

def reversed_list(list_to_sort):
    ordered_list = sorted(list_to_sort)
    ordered_list.reverse()
    return ordered_list

#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: tim_sort(list_to_sort)

bs2 = lambda: bubble_sort(ordered_list)
ms2 = lambda: merge_sort(ordered_list)
ts2 = lambda: tim_sort(ordered_list)

bs3 = lambda: bubble_sort(tiny_list)
ms3 = lambda: merge_sort(tiny_list)
ts3 = lambda: tim_sort(tiny_list)

bs4 = lambda: bubble_sort(nearly_ordered(list_to_sort))
ms4 = lambda: merge_sort(nearly_ordered(list_to_sort))
ts4 = lambda: tim_sort(nearly_ordered(list_to_sort))

bs5 = lambda: bubble_sort(reversed_list(list_to_sort))
ms5 = lambda: merge_sort(reversed_list(list_to_sort))
ts5 = lambda: tim_sort(reversed_list(list_to_sort))


#time the functions for 100 runs each
print("Using an unordered list")
print("Merge took:")
print(timeit(ms, number = 100))
print("Bubble took:")
print(timeit(bs, number = 100))
print("Timsort took:")
print(timeit(ts, number = 100))

print("Using an ordered list")
print("Merge took:")
print(timeit(ms2, number = 100))
print("Bubble took:")
print(timeit(bs2, number = 100))
print("Timsort took:")
print(timeit(ts2, number = 100))

print("Using a tiny list")
print("Merge took:")
print(timeit(ms3, number = 100))
print("Bubble took:")
print(timeit(bs3, number = 100))
print("Timsort took:")
print(timeit(ts3, number = 100))

print("Using a nearly sorted list")
print("Merge took:")
print(timeit(ms4, number = 100))
print("Bubble took:")
print(timeit(bs4, number = 100))
print("Timsort took:")
print(timeit(ts4, number = 100))

print("Using a reversed list")
print("Merge took:")
print(timeit(ms5, number = 100))
print("Bubble took:")
print(timeit(bs5, number = 100))
print("Timsort took:")
print(timeit(ts5, number = 100))

# https://pastebin.com/E9YjSk1Z