Merge-Sort (Komplexität)

Anzahl der Vergleiche?

$$T(1)=0, T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2\rceil) + (n-1)$$

Beispiele:

$$\begin{array}{c\vert cccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6... ...hline T(n)& 0 & 1 & 3 & 5 & 8 & 11 & 14 & 17 & 21 \end{array}$$

Übung: beweise durch Induktion $T(2^k) = 1 + (k-1) \cdot 2^k$.

Mit $n = 2^k$, also $k = \log_2 n$ folgt $T(n) \approx n \log_2 n$.

D. h. Merge-Sort ist asymptotisch besser als Bubble-Sort.