Merge-Sort (Komplexität)

Anzahl der Vergleiche?

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

Beispiele:

n123456789 
T(n)0135811141721 

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

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

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



Johannes Waldmann 2009-01-12