\input zb-basic
\input zb-matheduc
\iteman{ZMATH 2014b.00904}
\itemau{Rinderknecht, Christian}
\itemti{A didactic analysis of merge sort.}
\itemso{Teach. Math. Comput. Sci. 11, No. 2, 195-210 (2013).}
\itemab
Summary: Due to technical difficulties, educators who teach merge sort often avoid the analysis of the costs in the general and the average case. Using basic discrete mathematics, elementary real analysis and mathematical induction, we propose a self-contained derivation of bounds $\alpha n\log_2 n + \beta n + \gamma$ in all cases. Independently of any programming language or pseudo-code and supported by intuitive figures, it is suitable for informatics students interested in the analysis of algorithms. It is also a good exercise in showing that induction allows to discover constants instead of simply checking them a posteriori.
\itemrv{~}
\itemcc{P25 N75 K25}
\itemut{didactics of informatics; analysis of algorithms; cost analysis; merging; merge sort; enumerative combinatorics}
\itemli{}
\end