# Voegt de (geordende) bestanden transacties-1.txt en transacties-2.txt samen
# tot één enkel bestand met merge-sort.

transacties = []

with open("transacties-1.txt", "r") as bestand_1:
    transacties = bestand_1.readlines()


with open("transacties-2.txt", "r") as bestand_2:
    transacties.extend(bestand_2.readlines())
    

def samenvoegen (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(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)


transacties = merge_sort(transacties)

with open("transacties.txt", "w") as bestand_3:
    for transactie in transacties:
        print(transactie, file = bestand_3, end='')