from random import randint
from time import time

# samenvoegen van twee geordende lijsten  
def samenvoegen(lijst_1, lijst_2):
    resultaat = []
    
    # hoofdlus
    while len(lijst_1) > 0 and len(lijst_2) > 0:
        if lijst_1[0] < lijst_2[0]:
            resultaat.append(lijst_1.pop(0))
        else:
            resultaat.append(lijst_2.pop(0))
    
    # behandel wat er overblijft van lijst_1
    resultaat += lijst_1
    
    # behandel wat er overblijft van lijst_2
    resultaat += lijst_2

    return resultaat


def merge_sort(lijst):
    lengte = len(lijst)
    if lengte < 2:
        return lijst
    else:
        halve_lengte = lengte // 2
        eerste_helft = merge_sort(lijst[:halve_lengte])
        tweede_helft = merge_sort(lijst[halve_lengte:])
        return samenvoegen(eerste_helft, tweede_helft)
    

def insertion_sort(lijst):
    for lengte in range(1,len(lijst)):
        getal = lijst[lengte]
        index = lengte - 1
        while index >= 0 and lijst[index] > getal:
            lijst[index+1] = lijst[index]
            index -= 1
        lijst[index+1] = getal

# TIJDSMETING

print("merge sort     insertion sort")

for n in range(5000, 15000, 1000):
    
    # een willekeurige lijst van n getallen in het bereik [0,n]
    lijst = []
    for _ in range(n):
        lijst.append(randint(0,n))
    
    # tijdsmeting merge sort 
    start = time()
    merge_sort(lijst)     
    tijd_merge_sort = time() - start
    
    # de oorspronkelijke lijst bestaat na de merge sort nog steeds
    # tijdsmeting insertion sort
    start = time()
    insertion_sort(lijst)
    tijd_insertion_sort = time()-start
    
    # afdrukken
    print(f"{tijd_merge_sort:.4f}         {tijd_insertion_sort:.4f}")  # 4 cijfers na de komma