bubble sort, merge sort, timsort, timeit

# -*- coding: utf-8 -*-
"""
Created on Thu Feb 14 13:44:14 2019

@author: Naomi Toshiba
"""

from timeit import timeit
from random import randint

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


def tbubble_sort(seq):
    """Inefficiently sort the mutable sequence (list) in place.
       seq MUST BE A MUTABLE SEQUENCE.

       As with list.sort() and random.shuffle this does NOT return
    """
    changed = True
    while changed:
        changed = False
        for i in range(len(seq) - 1):
            if seq[i] > seq[i+1]:
                seq[i], seq[i+1] = seq[i+1], seq[i]
                changed = True
    return seq



def merge1(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

    return list_c


def merge_sort1(unsorted):
    if len(unsorted) < 2:
        return unsorted
    else:
        middle = len(unsorted) // 2
        front = unsorted[:middle]
        back = unsorted[middle:]

        front = merge_sort1(front)
        back = merge_sort1(back)
    return merge1(front, back)




##################################################################



#Generate a large (4500 items) random list
list_to_sort = [randint(0,100000) for i in range(4500)]

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

#time the functions for 100 runs each
print('A list of 4500 numbers 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(tis,number=100))