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

• Een eenvoudige strategie voegt verschillende lijsten samen via een merge methode. 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 methode public List<Integer> mergeA(List<List<Integer>> lists).
• Een efficiënter algoritme maakt gebruik van verdeel en heers. Schrijf hiervoor een recursief algoritme in de methode public List<Integer> mergeB(List<List<Integer>> lists).
• Een betere strategie qua geheugencomplexiteit gebruikt een prioriteitswachtlijn. Dit algoritme implementeer je in de methode public List<Integer> mergeC(List<List<Integer>> lists).

Deze methoden schrijf je in een klasse KWayMerge, die een implementatie is van de gegeven interface Merge¹. Al deze methoden nemen een lijst van gesorteerde lijsten als input en geeft een lijst terug met daarin alle oorspronkelijke elementen, ook gesorteerd.

Opmerking: pas de input niet aan. Indien je dit wel doet, zullen de testen falen.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.