Bitonic Mergesort, Variante 2 (1: breadth first)

Hierbei handelt es sich um eine alternative Variante (Teil 1). Sie liefert das typische Bild eines "breadth first"-Algorithmus. Diese Variante kann nur angewendet werden, wenn die Feldgröße (n) eine 2er-Potenz ist. Abwandlungen für beliebige Feldgrößen sind möglich.

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

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

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

mergesort(field A, int l, int r) {
  for m:= 2 to r-l+1 step m do {
    asc:= true;
    for i:= l to r step m do parallel {
      merge(A, i, i+m-1, asc);
      asc:= not asc;
    }
  }
}

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


Bitonic Mergesort, Variante 2+5


Bitonic Mergesort, Variante 2+6