def merge(list_a, list_b):
  list_sorted = []
  while list_a and list_b:
    if list_a[0] < list_b[0]:
      list_sorted.append(list_a.pop(0))
    else:
      list_sorted.append(list_b.pop(0))
  if list_a:
    list_sorted += list_a
  else:
    list_sorted += list_b
  return list_sorted

def merge_sort(unsorted):
  # unsorted is a list
  length = len(unsorted)
  if length <= 1:
    return unsorted
  middle = length//2
  front = merge_sort(unsorted[:middle])
  back = merge_sort(unsorted[middle:])
  return merge(front, back)

def bubble_sort(unsorted):
  sorted = unsorted[:]  # copy the unsorted list
  ran = range(len(sorted)-1)
  swapped = True
  while swapped:
    swapped = False
    for i in ran:
      # compare items with indices i and i+1:
      if sorted[i] > sorted[i+1]:
        sorted[i], sorted[i+1] = sorted[i+1], sorted[i]
        swapped = True
  return sorted

from timeit import timeit # requires Python 3!
from random import randint

# Create anonymous functions to use with timeit:
bs = lambda: bubble_sort(list_to_sort)
ms = lambda: merge_sort(list_to_sort)
ts = lambda: sorted(list_to_sort)

for i in range(1,4):
  n = 10**i
  # Generate a large (n items) random list
  list_to_sort = [randint(0,100000) for i in range(n)]
  list_to_sort = sorted(list_to_sort)

  # Time the functions for 100 runs each
  print("Timsort of {} items took:".format(n))
  print(timeit(ts, number = 100))

  print("Merge_sort of {} items took:".format(n))
  print(timeit(ms, number = 100))

  print("Bubble_sort of {} items took:".format(n))
  print(timeit(bs, number = 100))