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
|