In der Vorlesung wurder der Algorithmus Mergesort bereits iterativ implementiert. In dieser Aufgabe sollen Sie ihn auf rekursive Weisestinsetzen. Implementieren Sie dazu die Funktion mergesort im gegebenen Coderahmen. Die Funktion hat folgende Signatur:

void mergesort$($int values$[],$ int first$\_$index, int last$\_$index$)$

Die Funktion soll den Bereich von first$\_$index bis last$\_$index durch Aufruf von sich selbst sortieren und dabei die bekannte Funktion merge nutzen. Zur Erinnerung: Die Funktion merge nimmt die f$$nf Argumente $a,b,c,la$ und $lb$ entgegen. a und $b$ sind sortierte Felder der L$$ngen $la$ bzw$.$ Ib$.c$ ist ein $($leeres$)$ Feld, in das das Ergebnis des Zusammenf$$gens geschrieben wird.

Wichtig: Implementieren Sie die Funktion rekursiv! Dies bedeutet, dass die Funktion sich selbst aufruft, anstatt $$ber das Feld zu iterieren. Setzten Sie die Funktion durch Implementieren der folgenden Schritte bzw$.$ Regeln um:

Falls der Bereich die L$$nge $1$ hat, braucht er nicht weiter unterteilt zu werden und ist automatisch sortiert.

Im Rekursionsschritt sollten Sie den zu sortierenden Bereich in zwei H$$lften teilen und auf beiden einen rekursiven Aufruf starten.

Sobald Sie sicher sind$,$ dass die zwei Bereiche sortiert sind$,$ k$$nnen sie einfach die Funktion merge nutzen, um sie zusammenzuf$$gen$.$

Tipp: Falls Sie Schwierigkeiten haben, auf eine L$$sungsidee zu kommen, entwickeln Sie zun$$chst einen Algorithmus f$$r ein Feld der L$$nge $1.$ Erweitern Sie ihn anschlie$$end so$,$ dass er mit einem Feld der L$$nge $2$ funktioniert. Erweitern Sie dann f$$r Felder der L$$nge $4$ und stellen anschlie$$end sicher, dass auch Felder der L$$nge $3$ sortiert werden. $$berlegen Sie dann, ob und ggf$.$ was noch f$$r beliebig lange Felder fehlt und welche der o$.$ g$.$ Schritte noch noch umgesetzt werden m$$ssen$.$

Wichtig:

Verwenden Sie die an diese Aufgabe angeh$$ngte Datei mergesort$\_$recursive.cpp$.$ Implementieren Sie die Funktion darin und geben sie anschlie$$end ab$.$

Achtung: Das bestehen der Testf$$lle in der main$-$Funktion garantiert nicht, dass Ihre L$$sung richtig ist. Wir werden f$$r die Bewertung noch weitere F$$lle testen.

Sie d$$rfen davon ausgehen, dass first$\_$index last$\_$index gilt.

Ihr Code darf keine Eingaben entgegennehmen oder Ausgaben erzeugen.

Sie d$$rfen den Coderahmen nur an den markierten Stellen und innerhalb der main$-$Funktion ver$$ndern$.$

Stellen Sie sicher, dass Ihr Programm die o$.$g$.$ Signaturen verwendet.