Mergesort, Variante 3 (1: natürliches Mergesort)

Hierbei handelt es sich um eine alternative verbesserte Variante (Teil 1). Sie liefert das typische Bild eines "breadth first"-Algorithmus. Diese Variante wird häufig auch als "natürliches Mergesort" bezeichnet. Das Prinzip ist einfach: Es werden natürlich sortierte Folgen gesucht. Dadurch werden Vergleichsoperationen eingespart.

Eine rekursive Realisierung (Variante 3.b) ist möglich.

Diese Variante muß noch mit einer anderen Variante (ab 4) kombiniert werden.

Variante 3.a (iterativ)
Typ alternativ, optimiert
Eigenschaften iterativ, ???, ???, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n) Θ(nlogn) Ο(nlogn)
Vergleiche ??? ??? ???
Vertauschungen ??? ??? ???

mergesort(field A, int l, int r) {
  do {
    i:= l;
    do {
      k:= i;
      while (i < r) and (A[i] <= A[i+1]) do {
        i++;
      }
      q:= i;
      do {
        i++;
      } while (i < r) and (A[i] <= A[i+1]);
      if (i <= r) then {
        merge(A, k, q, i);
      }
    } while (i <= r);
  } while (k > l);
}

merge(field A, int l, int q, int r) {
  ...
}


Mergesort, Variante 3+5


Mergesort, Variante 3+6