Mergesort: Zeitkomplexität am Beispiel eines Feldes mit 8 Elementen 12 34 65 23 17 33 20 8 12 23 17 8 4 sortierte 2er Stapel 34 65 33 20 12 8 2 sortierte 4er Stapel 23 17 34 20 65 33 8 1 sortierter 8er Stapel 12 17 20 23 33 34 65 In jeder "Runde" wird jedes Element "angefasst" (~ n). Es gibt hier 3 Runden. Wenn es 16 Elemente wären, gäbe es eine Runde mehr, also 4 = ld 16 (~ log n). Zusammengefasst: t ~ n * log n