Gegeven zijn \(k\) gesorteerde lijsten. Gevraagd wordt om deze lijsten samen te voegen tot één lijst. Dit kan op verschillende manieren geïmplementeerd worden:

• Een eenvoudige strategie voegt verschillende lijsten samen via een merge(rij1: list, rij2: list) functie. Om te beginnen worden de eerste twee lijsten gemerged, hierna wordt deze lijst gemerged met de derde lijst, en zo verder. Dit algoritme moet worden geïmplementeerd in de functie mergeA(lists: list).
• Een efficiënter algoritme maakt gebruik van verdeel en heers. Schrijf hiervoor een recursief algoritme in de functie mergeB(lists: list).
• Een betere strategie qua geheugencomplexiteit gebruikt een prioriteitswachtlijn. Dit algoritme implementeer je in de functie mergeC(lists: list).

Al deze methoden nemen een lijst van lijsten als input en geven de gemergede lijst van deze lijsten terug.

>>> mergeA([[1, 3, 5], [0, 2, 4], [1, 8, 9, 10, 11]])
[0, 1, 1, 2, 3, 4, 5, 8, 9, 10, 11]
>>> mergeA([[1, 10, 20, 100], [99, 101, 200, 400], []])
[1, 10, 20, 99, 100, 101, 200, 400]

>>> mergeB([[1, 3, 5], [0, 2, 4], [1, 8, 9, 10, 11]])
[0, 1, 1, 2, 3, 4, 5, 8, 9, 10, 11]
>>> mergeB([[1, 10, 20, 100], [99, 101, 200, 400], []])
[1, 10, 20, 99, 100, 101, 200, 400]

>>> mergeC([[1, 3, 5], [0, 2, 4], [1, 8, 9, 10, 11], []])
[0, 1, 1, 2, 3, 4, 5, 8, 9, 10, 11]
>>> mergeC([[1, 10, 20, 100], [99, 101, 200, 400]])
[1, 10, 20, 99, 100, 101, 200, 400]