@article {MATHEDUC.06257398,
author = {Rinderknecht, Christian},
title = {A didactic analysis of merge sort.},
year = {2013},
journal = {Teaching Mathematics and Computer Science},
volume = {11},
number = {2},
issn = {1589-7389},
pages = {195-210},
publisher = {,},
abstract = {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.},
msc2010 = {P25xx (N75xx K25xx)},
identifier = {2014b.00904},
}