# 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 = len(lijst)//2
        eerste_helft = merge_sort(lijst[:halve_lengte])
        tweede_helft = merge_sort(lijst[halve_lengte:])
        return samenvoegen(eerste_helft,tweede_helft)


# Een aantal testen:
lijst = [4, 14, 9, 10, 6, 0, 7, 13, 3, 14, 2, 11, 1, 0, 12, 8, 5, 9]
print(merge_sort(lijst))

lijst = [17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
print(merge_sort(lijst))

lijst = [2, 1]
print(merge_sort(lijst))

lijst = [1]
print(merge_sort(lijst))

lijst = []
print(merge_sort(lijst))