Mergesort

Mergesort für das Wort "informatik"

nicht relevant fürs Zentralabitur!

Funktionsweise

Mergesort ist ein Divide&Conquer-Verfahren.

Im Divide wird die Liste in zwei gleich große Teile aufgeteilt (wenn die Anzahl der Elemente ungerade ist, dann natürlich nicht ganz gleich groß...).

Beim Conquer werden die sortierten Teillisten zusammengefügt. Durch geschickte Implementierung kann man das in O(n) Zeit bewerkstelligen.

Laufzeit

Mergesort hat auch im Worst Case eine Laufzeit von O(n*log(n)).
Für Arrays ist allerdings Quicksort schneller, weil man bei Mergesort ständig neue Arrays erzeugen muss - bei Quicksort dagegen kann man in situ (bzw. in place) arbeiten.

Implementierung

public List<String> mergesort(List<String> pList){
  List<String> ergebnis = new List<>();
  List<String> links = new List<>();
  List<String> rechts = new List<>();
  // Abbruchbedingung: nur 1 Element in pList
  pList.toFirst();
  pList.next();
  if(pList.hasAccess() == false) {
     return pList;
  }
  // verteilen auf links und rechts
  boolean nachLinks = true;
  for(pList.toFirst(); pList.hasAccess(); pList.next()) {
     String s = pList.getContent();
     if(nachLinks == true) {
        links.append(s);
        nachLinks = false;
     }
     else {
        rechts.append(s);
        nachLinks = true;
     }
  }
  //sortieren der Teillisten durch rekursive Aufrufe
  List<String> linksSortiert = mergesort(links);
  List<String> rechtsSortiert = mergesort(rechts);  
  // die beiden sortierten Listen zu einer einzigen verschmelzen
  ergebnis = merge(linksSortiert, rechtsSortiert);
  return ergebnis;
}	

Die folgende Hilfs-Methode verschmilzt zwei sortierte Listen zu einer einzigen.

private List<String> merge(List<String> l1, List<String> l2) {
  List<String> ergebnis = new List<>();
  l1.toFirst();
  l2.toFirst();
  // beide Listen parallel durchlaufen
  while(l1.hasAccess() && l2.hasAccess()){
     // jeweils die erste String auslesen
     String s1 = l1.getContent();
     String s2 = l2.getContent();
     // die alphabetisch kleinere der beiden Strings
     // in die Liste ergebnis uebertragen
     // und in der Herkunftsliste eins weiter gehen
     if(s1.compareTo(s2) < 0){
        ergebnis.append(s1);
        l1.next();
     }
     else{
        ergebnis.append(s2);
        l2.next();
     }
  }
  // den Rest der ersten Liste (wenn es einen gibt)
  // in ergebnis uebertragen
  while(l1.hasAccess()){
     ergebnis.append(l1.getContent());
     l1.next();
  }
  // den Rest der zweiten Liste (wenn es einen gibt)
  // in ergebnis uebertragen
  while(l2.hasAccess()){
     ergebnis.append(l2.getContent());
     l2.next();
  }
  return ergebnis;
}