Bitonic 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, stabil, ???
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 r, bool asc) {
  for i:= l to r do parallel {
    B[0][i]:= i;
    B[1][i]:= i;
  }
  if asc then {
    k:=  l;
    c:= +1;
  } else {
    k:=  r;
    c:= -1;
  }
  i:= l;
  j:= r;
  while (i < j) do {
    s:= B[0][i];
    t:= B[0][j];
    if (A[s] < A[t]) or (asc and (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;
    k:= k + c;
  }
}


Bitonic Mergesort, Variante 1+6


Bitonic Mergesort, Variante 2+6