MSsort, Variante 1 (Grundgerüst, Beispiel)

Hierbei handelt es sich um das Grundgerüst. Das Prinzip wird im Folgenden an der Standardvariante von Bubblesort demonstriert.

Die best-case-Laufzeiten betreffen nicht dieses Beispiel, sondern den Idealfall (Verwendung der optimalsten Algorithmen).

Die Split-Operation wird hier implizit realisiert, da nur Nachbarverschmelzungen stattfinden. Im Speicher muß maximal ein Feld der Größe "2m" gehalten werden!

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

Variante 1.a (iterativ)
Typ standard, Beispiel
Eigenschaften iterativ, in-place, stabil, parallelisierbar
Datenstrukturen Felder, Listen
Speicher Ω(m) Θ(m) Ο(m)
Laufzeit (p) Ω(mlog(n²/m)) Θ(2n-2m-n/m) Ο(2n-2m-n/m)
Laufzeit Ω(nlog(n²/m)) Θ(nm/2+n²/m) Ο(nm/2+n²/m)
Vergleiche nlog(n²/m) nm/2+n²/m nm/2+n²/m
Vertauschungen 0 nm/4+n²/m/2 nm/2+n²/m
Hinweis Die Feldgröße n (r-l+1) muß durch m teilbar sein.
mssort(field A, int l, int r, int m) {
  for i:= l to r-m+1 step m do parallel {
    sort1(A, i, i+m-1);
  }
  sort2(A, l, r, m);   
}

sort1(field A, int l, int r) {
  // Ein beliebiges Sortierverfahren
  for i:=r downto l+1 do {
    for j:=l to i-1 do {
      if (A[j] > A[j+1]) then {
        exchange(A[j], A[j+1]);
      }
    }
  }
}

sort2(field A, int l, int r, int m) {
  // Ein beliebiges modifiziertes Sortierverfahren
  for i:=r-m+1 downto l+m step m do {
    for j:=l to i-m step m do {
      merge(A, j, j+m-1, j+2*m-1);
    }
  }
}

merge(field A, int l, int q, int r) {
  // Eine beliebige Merge-Operation
  // Siehe Mergesort, BTMsort, Bitonicsort, ...
}


MSsort, Variante 1