Mergesort, Variante 6 (2: Tepif)

Hierbei handelt es sich um eine alternative, verbesserte Variante. Die Idee ist einfach: Ein temporäres Indexfeld (bidirektional) spart Speicherplatz, Kenntnisse über die Elemente und reduziert das Risiko eines Datenverlustes (da in-place).

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

Variante 6.a (iterativ)
Typ optimiert
Eigenschaften iterativ, in-place, instabil, ???
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche nlogn nlogn nlogn
Verschiebungen 0 nlogn nlogn

mergesort(field A, int l, int r) {
  ...
}

merge(field A, int l, int q, int r) {
  for i:= l to q do parallel {
    B[0][i]:= i;
    B[1][i]:= i;
  }
  for j:= q+1 to r do parallel {
    B[0][j]:= r+q+1-j;
    B[1][j]:= r+q+1-j;
  }
  i:= l;
  j:= r;
  for k:= l to r-1 do {
    s:= B[0][i];
    t:= B[0][j];
    if (A[s] <= A[t]) then {
      i++;
    } else {
      s:= t;
      j--;
    }
    exchange(A[k], A[s]);
    t:= B[1][k];
    B[0][t]:= s;
    B[1][s]:= t;
  }
}


Mergesort, Variante 1+6


Mergesort, Variante 2+6