import time

def mergesort(L):
    if len(L)>1:
        centr = len(L)//2
        levaya = L[:centr] 
        pravaya = L[centr:]

        mergesort(levaya)
        mergesort(pravaya)

        i=0
        j=0
        k=0
        while i < len(levaya) and j < len(pravaya):
            if levaya[i] < pravaya[j]:
                L[k]=levaya[i]
                i=i+1
            else:
                L[k]=pravaya[j]
                j=j+1
            k=k+1

        while i < len(levaya):
            L[k]=levaya[i]
            i=i+1
            k=k+1

        while j < len(pravaya):
            L[k]=pravaya[j]
            j=j+1
            k=k+1
    return L


def print_times(L):
	print("{0:7}".format(len(L)), end=":")
	L_copy = L[:]
	t1 = time.perf_counter()
	mergesort(L_copy)
	t2 = time.perf_counter()
	print("{0:10.1f}".format((t2-t1)*1000.), end='')
	print()


import random
for list_size in [50, 100, 2000, 3000]:
    L = list(range(list_size))
    random.shuffle(L)
    print_times(L)