
06257398
j
2014b.00904
Rinderknecht, Christian
A didactic analysis of merge sort.
Teach. Math. Comput. Sci. 11, No. 2, 195210 (2013).
2013
,
EN
P25
N75
K25
didactics of informatics
analysis of algorithms
cost analysis
merging
merge sort
enumerative combinatorics
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 selfcontained derivation of bounds $\alpha n\log_2 n + \beta n + \gamma$ in all cases. Independently of any programming language or pseudocode 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.