Bitonic Mergesort, Variante 4 (2: Original)

Hierbei handelt es sich um die Original-Variante (Teil 2).

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

In Verbindung mit Variante 2/3 sind weitere Optimierungen möglich, indem "merge" Elemente ausschließlich in eine Richtung (von Feld A nach Feld B oder umgekehrt) kopiert.

Variante 4.a (iterativ)
Typ standard
Eigenschaften iterativ, out-of-place, stabil, ???
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche nlogn nlogn nlogn
Kopierungen 2nlogn 2nlogn 2nlogn

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

merge(field A, int l, int r, bool asc) {
  for i:=l to r do parallel {
    B[i]:= A[i];
  }
  if asc then {
    k:=  l;
    c:= +1;
  } else {
    k:=  r;
    c:= -1;
  }
  i:= l;
  j:= r;
  while (i <= j) do {
    if (B[i] < B[j]) or (asc and (B[i] = B[j])) then {
      A[k]:= B[i];
      i++;
    } else {
      A[k]:= B[j];
      j--;
    }
    k:= k + c;
  }
}


Bitonic Mergesort, Variante 1+4


Bitonic Mergesort, Variante 2+4