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


# testen
lijst_1 = [1,2,4,5,8,9,11]
#lijst_2 = [3,6,7,10,12]
# of met een tweede lijst die langer is dan de eerste:
lijst_2 = [0,3,6,7,10,12,13,14]

# resultaat kan gemakkelijk gecontroleerd worden
print(samenvoegen(lijst_1,lijst_2))

#--------------------------------------------------------------
# Volledige in-place versie wordt behandeld in de oefeningen
# op het einde van het hoofdstuk
#--------------------------------------------------------------
# def samenvoegen (lijst_1, lijst_2):
#     resultaat = [0] * (len(lijst_1) + len(lijst_2))
#     index_1 = 0
#     index_2 = 0
#     index_3 = 0       # gebruikt voor resultaat
# 
#     # hoofdlus
#     while index_1 < len(lijst_1) and index_2 < len(lijst_2):
#         if lijst_1[index_1] < lijst_2[index_2]:
#             resultaat[index_3] = lijst_1[index_1]
#             index_1 += 1
#         else:
#             resultaat[index_3] = lijst_2[index_2]
#             index_2 += 1
#         index_3 += 1      # niet vergeten!
# 
#     # behandel wat er overblijft van lijst_1
#     while index_1 < len(lijst_1):
#         resultaat[index_3] = lijst_1[index_1]
#         index_1 += 1
#         index_3 += 1
# 
#     # behandel wat er overblijft van lijst_2
#     while index_2 < len(lijst_2):
#         resultaat[index_3] = lijst_2[index_2]
#         index_2 += 1
#         index_3 += 1
# 
#     return resultaat
#--------------------------------------------------------------