Mergesort, Variante 4 (2: Original)

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

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

Variante 4.a (iterativ)
Typ standard
Eigenschaften iterativ, out-of-place, instabil, ???
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 q, int r) {
  for i:=l to q do parallel {
    B[i]:= A[i];
  }
  for j:=q+1 to r do parallel {
    B[r+q+1-j]:= A[j];
  }
  i:= l;
  j:= r;
  for k:=l to r do {
    if (B[i] <= B[j]) then {
      A[k]:= B[i];
      i++;
    } else {
      A[k]:= B[j];
      j--;
    }
  }
}


Mergesort, Variante 4