from random import randint
from time import time


# samenvoegen van twee geordende lijsten: de eenvoudigste oplossing
def samenvoegen_eenvoudig(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


# samenvoegen van twee geordende lijsten: in-place oplossing
def samenvoegen_inplace(lijst_1, lijst_2):
    resultaat = [0] * (len(lijst_1) + len(lijst_2))
    index_lijst_1 = 0
    index_lijst_2 = 0
    index_resultaat = 0

    # hoofdlus
    while index_lijst_1 < len(lijst_1) and index_lijst_2 < len(lijst_2):
        if lijst_1[index_lijst_1] <= lijst_2[index_lijst_2]:
            resultaat[index_resultaat] = lijst_1[index_lijst_1]
            index_lijst_1 += 1
        else:
            resultaat[index_resultaat] = lijst_2[index_lijst_2]
            index_lijst_2 += 1
        index_resultaat += 1
        
    # behandel wat er overblijft van lijst_1
    while index_lijst_1 < len(lijst_1):
        resultaat[index_resultaat] = lijst_1[index_lijst_1]
        index_lijst_1 += 1
        index_resultaat += 1
        
    # behandel wat er overblijft van lijst_2
    while index_lijst_2 < len(lijst_2):
        resultaat[index_resultaat] = lijst_2[index_lijst_2]
        index_lijst_2 += 1
        index_resultaat += 1

    return resultaat


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


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

print("merge sort    merge sort met inplace samenvoegen")
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))
    
    # timing merge sort met eenvoudig samenvoegen 
    start = time()
    merge_sort_samenvoegen_eenvoudig(lijst)
    tijd_merge_sort_eenvoudig = time()-start
    
    # timing merge sort met inplace samenvoegen
    start = time()
    merge_sort_samenvoegen_inplace(lijst)
    tijd_merge_sort_inplace = time()-start

    # afdrukken
    print(f"{tijd_merge_sort_eenvoudig:.4f}        {tijd_merge_sort_inplace:.4f}")  # 4 cijfers na de komma