Mergesort, Variante 5 (2: Listen-Optimierung)

Hierbei handelt es sich um eine verbesserte Variante, die besonders für Listen geeignet ist. Die Idee ist einfach: Bei Listen sind Verschiebungen billiger als Vertauschungen. Außerdem werden weniger Bewegungsopterationen benötigt und das Verfahren ist dann nicht mehr out-of-place.

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

Variante 5.a (iterativ)
Typ optimiert
Eigenschaften iterativ, in-place, stabil, ???
Datenstrukturen einfachverkettete Listen (?)
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche nlogn/2 n(logn-1.25) nlogn
Verschiebungen 0 nlogn/2.3 nlogn/2

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

merge(field A, int l, int q, int r) {
  q++;
  while (l < q) and (q <= r) do {
    if (A[l] > A[q]) then {
      move(A[q], A[l]);
      q++;
    }
    l++;
  }
}


Mergesort, Variante 1+5


Mergesort, Variante 2+5