MergeSort ist wie QuickSort ein rekursiver Sortieralgorithmus.
Die grundlegende Idee des MergeSort-Algorithmus ist die, dass das zu sortierende Array in zwei Teil-Arrays zerlegt wird und diese durch rekursive Anwendung des Algorithmus sortiert und anschließend gemischt werden. Die Rekursion endet, wenn ein Teil-Array nur noch aus einem Element besteht. In diesem Fall ist es ja sortiert.
Mischen zweier sortierter Teil-Arrays bedeutet, dass diese zu einem sortierten Array verschmolzen werden. Dazu werden die Teil-Arrays zunächst in ein Hilfs-Array kopiert. Anschließend werden die beiden Teil-Arrays elementweise durchlaufen. Das jeweils kleinere Element wird zurückkopiert. Zum Schluss muss dann noch der Rest eines der beiden Teil-Arrays zurückkopiert werden.
Die folgende Klasse MergeSort (MergeSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des MergeSort-Algorithmus:
public class MergeSort implements SortierAlgorithmus {
private int[] hilfsArray;
// sortiert das uebergebene Array in aufsteigender Reihenfolge
// gemaess dem MergeSort-Algorithmus
public void sortiere(int[] zahlen) {
hilfsArray = new int[zahlen.length];
mergeSort(zahlen, 0, zahlen.length-1);
}
// der MergeSort-Algorithmus wird auf dem Array zwischen den
// angegebenen Indizes ausgefuehrt
private void mergeSort(int[] zahlen, int linkerIndex, int rechterIndex) {
if (linkerIndex < rechterIndex) {
int mittlererIndex = (linkerIndex + rechterIndex) / 2;
mergeSort(zahlen, linkerIndex, mittlererIndex);
mergeSort(zahlen, mittlererIndex+1, rechterIndex);
mischen(zahlen, linkerIndex, mittlererIndex, rechterIndex);
}
}
// mischt die zwei (sortierten) Teil-Arrays von linkerIndex bis
// mittlererIndex und mittlererIndex+1 bis rechterIndex
private void mischen(int[] zahlen, int linkerIndex, int mittlererIndex,
int rechterIndex) {
// beide Teil-Arrays in das Hilfsarray kopieren
for (int i=linkerIndex; i<=rechterIndex; i++) {
hilfsArray[i] = zahlen[i];
}
// jeweils das kleinere Element der beiden Teil-Arrays zurückkopieren
int linkerZeiger = linkerIndex;
int rechterZeiger = mittlererIndex + 1;
int aktuellerZeiger = linkerIndex;
while (linkerZeiger <= mittlererIndex && rechterZeiger <= rechterIndex) {
if (hilfsArray[linkerZeiger] <= hilfsArray[rechterZeiger]) {
zahlen[aktuellerZeiger++] = hilfsArray[linkerZeiger++];
} else {
zahlen[aktuellerZeiger++] = hilfsArray[rechterZeiger++];
}
}
// falls vorhanden Reste des ersten Teil-Arrays zurückkopieren
while (linkerZeiger <= mittlererIndex) {
zahlen[aktuellerZeiger++] = hilfsArray[linkerZeiger++];
}
// falls vorhanden Reste des zweiten Teil-Arrays zurückkopieren
while (rechterZeiger <= rechterIndex) {
zahlen[aktuellerZeiger++] = hilfsArray[rechterZeiger++];
}
}
}
Die folgende Hamster-Klasse MergeSortHamster (MergeSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den MergeSort-Algorithmus. Voraussetzung ist, dass es im Territorium drei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. In der ersten Reihe unterhalb der Körnerhaufenreihe markieren zwei Markierungshamster jeweils den linken und rechten Rand des aktuell betrachteten Teil-Arrays. Darunter die Reihe wird als Ablagereihe benutzt. Hierhin werden vor dem Mischen die Körnerhaufen der beiden beteiligten Teil-Arrays transportiert. Unterhalb dieser Reihe markieren zwei weitere Markierungshamster beim Mischen das jeweils betrachtete Element der beiden Teil-Arrays. Ein fünfter Markierungshamster (weiß) markiert in der ersten Reihe unterhalb der Körnerhaufenreihe die Kachel, in die jeweils beim Mischen der kleinere der beiden betrachteten Körnerhaufen der Teil-Arrays transportiert werden muss.
// Demonstration des MergeSort-Algorithmus
public class MergeSortHamster
extends KoernerHaufenSortierHamster
implements SortierHamster
{
private MarkierungsHamster linkerIndexHamster = null;
// markiert den linken Rand des aktuellen Teil-Arrays
private MarkierungsHamster rechterIndexHamster = null;
// markiert den rechten Rand des aktuellen Teil-Arrays
private MarkierungsHamster linkerZeigerHamster = null;
// markiert waehrend des Mischens das aktuell
// betrachtete Element des ersten Teil-Arrays
private MarkierungsHamster rechterZeigerHamster = null;
// markiert waehrend des Mischens das aktuell
// betrachtete Element des rechten Teil-Arrays
private MarkierungsHamster aktuellerZeigerHamster = null;
// markiert waehrend der Partitionierung das aktuell
// betrachtete rechte Element
private int anzahlKoernerHaufen = 0;
// Anzahl der zu sortierenden Koernerhaufen
// Konstruktor
public MergeSortHamster(boolean mitErlaeuterungen) {
super(mitErlaeuterungen);
this.erlaeuterung(
"Ich sortiere die Koernerhaufen auf der Basis des MergeSort-Algorithmus.");
this.linkerIndexHamster =
new MarkierungsHamster(this.getReihe()+1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.linkerIndexHamster.erlaeuterung(
"Ich markiere den linken Rand des aktuell betrachteten Teil-Arrays.");
this.rechterIndexHamster =
new MarkierungsHamster(this.getReihe()+1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.rechterIndexHamster.erlaeuterung(
"Ich markiere den rechten Rand des aktuell betrachteten Teil-Arrays.");
this.linkerZeigerHamster =
new MarkierungsHamster(this.getReihe()+3, this.getSpalte(),
this.getReihe()+2, mitErlaeuterungen);
this.linkerZeigerHamster.erlaeuterung(
"Ich markiere waehrend des Mischens das aktuell betrachtete Element\n" +
"des ersten Teils der Hilfskoernerhaufenreihe.");
this.rechterZeigerHamster =
new MarkierungsHamster(this.getReihe()+3, this.getSpalte(),
this.getReihe()+2, mitErlaeuterungen);
this.rechterZeigerHamster.erlaeuterung(
"Ich markiere waehrend des Mischens das aktuell betrachtete Element\n" +
"des zweiten Teils der Hilfskoernerhaufenreihe.");
this.aktuellerZeigerHamster =
new MarkierungsHamster(this.getReihe()+1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.aktuellerZeigerHamster.erlaeuterung(
"Ich markiere waehrend des Mischens das Element der Körnerhaufenreihe,\n" +
"in das die Körner der Hilfskoernerhaufenreihe zurueckkopiert werden.");
}
// Der Standard-Hamster steht mit Blickrichtung OST irgendwo im Territorium.
// Ein Vertretungshamster soll die Koernerhaufen bis zur nächsten Wand in
// aufsteigender Reihenfolge sortieren.
// Voraussetzung: Unterhalb des Standard-Hamsters existieren drei nicht
// durch Mauern blockierte Reihen.
public void sortiereKoernerHaufen() {
this.erlaeuterung(
"Ich zaehle nun die Anzahl der zu sortierenden Koernerhaufen.");
this.anzahlKoernerHaufen = this.ermittleAnzahlKoernerHaufen();
this.erlaeuterung(
"Die Anzahl der zu sortierenden Koernerhaufen betraegt " +
this.anzahlKoernerHaufen +
",\nd.h. die Indizes der Haufen liegen zwischen 0 und " +
(this.anzahlKoernerHaufen-1) +
".");
this.mergeSort(0, this.anzahlKoernerHaufen-1);
this.beendeSortierung();
}
// der MergeSort-Algorithmus wird auf dem Array zwischen den
// angegebenen Indizes ausgefuehrt
private void mergeSort(int linkerIndex, int rechterIndex) {
if (linkerIndex < rechterIndex) {
int mittlererIndex = (linkerIndex + rechterIndex) / 2;
mergeSort(linkerIndex, mittlererIndex);
this.erlaeuterung(
"Die Koernerhaufen von Index " +
linkerIndex + " bis " + mittlererIndex +
" sind (nun) sortiert.");
mergeSort(mittlererIndex+1, rechterIndex);
this.erlaeuterung(
"Die Koernerhaufen von Index " +
(mittlererIndex+1) + " bis " + rechterIndex +
" sind (nun) sortiert.");
mischen(linkerIndex, mittlererIndex, rechterIndex);
} else {
this.linkerIndexHamster.markiereIndex(linkerIndex);
this.rechterIndexHamster.markiereIndex(rechterIndex);
}
}
// mischt die zwei (sortierten) Teil-Arrays von linkerIndex bis
// mittlererIndex und mittlererIndex+1 bis rechterIndex
private void mischen(int linkerIndex, int mittlererIndex,
int rechterIndex) {
this.linkerIndexHamster.markiereIndex(linkerIndex);
this.rechterIndexHamster.markiereIndex(rechterIndex);
this.erlaeuterung(
"Es folgt nun das Mischen der Koernerhaufen von Index " +
linkerIndex + " bis " + mittlererIndex +
" und " +
(mittlererIndex+1) + " bis " + rechterIndex +
".\n" +
"Zunaechst werden dazu die Koernerhaufen in eine Hilfsreihe verschoben.");
// beide Teil-Arrays in das Hilfsarray (zwei Zeilen darunter) kopieren
int linkerZeiger = linkerIndex;
this.linkerZeigerHamster.markiereIndex(linkerZeiger);
int rechterZeiger = mittlererIndex + 1;
this.rechterZeigerHamster.markiereIndex(rechterZeiger);
for (int i=linkerIndex; i<=rechterIndex; i++) {
this.laufeZuIndex(i);
int koerner = this.nimmAlle();
this.setzeBlickrichtung(Hamster.SUED);
this.vor(2);
this.gib(koerner);
this.setzeBlickrichtung(Hamster.NORD);
this.vor(2);
}
// jeweils das kleinere Element der beiden Teil-Arrays zurückkopieren
int aktuellerZeiger = linkerIndex;
this.aktuellerZeigerHamster.markiereIndex(aktuellerZeiger);
this.erlaeuterung(
"Beim Mischen wird der kleinere der beiden markierten " +
"Koernerhaufen der Hilfsreihe an\ndie markierte Kachel der " +
"eigentlichen Reihe (weißer Markierungshamster) zurueckkopiert.");
while (linkerZeiger <= mittlererIndex && rechterZeiger <= rechterIndex) {
if (linkerZeigerHamster.liefereAnzahlKoerner() <=
rechterZeigerHamster.liefereAnzahlKoerner()) {
transportiereKoerner(linkerZeigerHamster.liefereIndex());
linkerZeiger++;
this.linkerZeigerHamster.markiereIndex(linkerZeiger);
} else {
transportiereKoerner(rechterZeigerHamster.liefereIndex());
rechterZeiger++;
this.rechterZeigerHamster.markiereIndex(rechterZeiger);
}
aktuellerZeiger++;
if (aktuellerZeiger <= rechterIndex) {
this.aktuellerZeigerHamster.markiereIndex(aktuellerZeiger);
}
}
// falls vorhanden Reste des ersten Teil-Arrays zurückkopieren
while (linkerZeiger <= mittlererIndex) {
transportiereKoerner(linkerZeigerHamster.liefereIndex());
linkerZeiger++;
this.linkerZeigerHamster.markiereIndex(linkerZeiger);
aktuellerZeiger++;
if (aktuellerZeiger <= rechterIndex) {
this.aktuellerZeigerHamster.markiereIndex(aktuellerZeiger);
}
}
// falls vorhanden Reste des zweiten Teil-Arrays zurückkopieren
while (rechterZeiger <= rechterIndex) {
transportiereKoerner(rechterZeigerHamster.liefereIndex());
rechterZeiger++;
this.rechterZeigerHamster.markiereIndex(rechterZeiger);
aktuellerZeiger++;
if (aktuellerZeiger <= rechterIndex) {
this.aktuellerZeigerHamster.markiereIndex(aktuellerZeiger);
}
}
}
// transportiert die Koerner aus
private void transportiereKoerner(int index) {
this.laufeZuIndex(index);
this.setzeBlickrichtung(Hamster.SUED);
this.vor(2);
int koerner = this.nimmAlle();
this.setzeBlickrichtung(Hamster.NORD);
this.vor(2);
this.laufeZuIndex(aktuellerZeigerHamster.liefereIndex());
this.gib(koerner);
}
private void beendeSortierung() {
this.laufeZuSpalte(this.startSpalte);
this.setzeBlickrichtung(Hamster.OST);
this.erlaeuterung("Sortierung erfolgreich beendet!");
}
}
Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitMergeSort) (SortierenMitMergeSort.ham) können Sie sich von den Hamstern den MergeSort-Algorithmus demonstrieren lassen.
void main() {
Hamster paul = Hamster.getStandardHamster();
String antwort =
Hamster.getStandardHamster().liesZeichenkette(
"Moechten Sie textuelle Erlaeuterungen (ja/nein)?");
SortierHamster sortierer = new MergeSortHamster(antwort.equals("ja"));
sortierer.sortiereKoernerHaufen();
}
Der MergeSort-Algorithmus ist stabil. MergeSort arbeitet nicht in-place.
MergeSort erfordert unabhängig vom Aufbau des zu sortierenden Arrays, d.h. auch
im unglücklichsten Fall, 
Vergleiche der Array-Elemente.
n ist dabei die Anzahl an zu sortierenden Elementen.
Allerdings ist zusätzlicher zu n proportionaler Speicherplatz erforderlich.
Im Web finden sich zahlreiche weitere Informationen zum MergeSort-Algorithmus, z.B. unter