# 

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)
    
# code overgenomen uit 4_samenvoegen_in_place    
def samenvoegen (lijst_1, lijst_2):
    resultaat = []
    index_1 = 0
    index_2 = 0

    # hoofdlus
    while index_1 < len(lijst_1) and index_2 < len(lijst_2):
        if lijst_1[index_1] < lijst_2[index_2]:
            resultaat.append(lijst_1[index_1])
            index_1 += 1
        else:
            resultaat.append(lijst_2[index_2])
            index_2 += 1

    # behandel wat er overblijft van lijst_1
    while index_1 < len(lijst_1):
        resultaat.append(lijst_1[index_1])
        index_1 += 1

    # behandel wat er overblijft van lijst_2
    while index_2 < len(lijst_2):
        resultaat.append(lijst_2[index_2])
        index_2 += 1

    return resultaat
   
# code overgenomen uit 3_isort_opl.py (hoofdstuk 9)
from random import randint;

def is_gesorteerd (lijst):
    index = 1;
    while index < len(lijst) and lijst[index-1] <= lijst[index]:
        index += 1
    return index >= len(lijst)

        
for _ in range(1000):
    # een willekeurige lijst van 20 gehele getallen in het bereik [0,30]
    lijst = []
    for __ in range(20):
        lijst.append(randint(0,30))
    lijst = merge_sort(lijst)
    if not is_gesorteerd(lijst):
        print ("Niet gesorteerd:", lijst)