Een eenvoudige implementatie van MergeSort maakt gebruik van recursie. De eerste en tweede helft van de lijst worden (recursief) afzonderlijk gesorteerd, waarna deze gesorteerde lijsten gemerged worden. In het volgende algoritme is de pseudocode gegeven:

MergeSort(a[1,..,n]):

	if length(a) >= 2:
	
	    MergeSort(a[0,..,(n-1)/2])
	    MergeSort(a[((n-1)/2)+1,..,n-1])
	    merge gesorteerde deelrijen
	    return gemergede rijen
	    
	else: return a

We willen nu dit algoritme implementeren zonder gebruik te maken van recursie. Hiervoor beginnen we met het mergen van aangrenzende elementen in de lijst, vervolgens mergen we de gesorteerde paren, enzovoort.

Om hiervoor een algoritme te schrijven, implementeer je de gegeven interface MergeSort¹ in een klasse NonRecursiveMergeSort. Implementeer hiervoor de methode public void sort(List<Integer> list), die als input een (ongesorteerde) lijst krijgt. Na uitvoering van het algoritme is deze lijst een gesorteerde versie van de oorspronkelijke lijst.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Hierin staan al enkele testen geschreven en kan je eenvoudig zelf extra testgevallen toevoegen.