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.

Implementeer hiervoor de methode sorteer(rij: list), die als input een (ongesorteerde) lijst krijgt. Na uitvoering van het algoritme is deze lijst een gesorteerde versie van de oorspronkelijke lijst.

Voorbeelden

>>> a = [4, 3, 2, 1]
>>> sorteer(a)
>>> a
[1, 2, 3, 4]
>>> a = [5, 2, 3, 0, 1, 4]
>>> sorteer(a)
>>> a
[0, 1, 2, 3, 4, 5]