Articles
A didactic analysis of merge sort
Published:
2013-12-01
Author
View
Keywords
didactics of informatics analysis of algorithms cost analysis merging merge sort enumerative combinatorics
License
Copyright (c) 2013 Christian Rinderknecht
This work is licensed under a Creative Commons Attribution 4.0 International License.
How To Cite
Selected Style:
APA
Rinderknecht, C. (2013). A didactic analysis of merge sort. Teaching Mathematics and Computer Science, 11(2), 195-210. https://doi.org/10.5485/TMCS.2013.0340
Abstract
Due to technical difficulties, educators teaching merge sort often avoid the analysis of the cost in the general and average cases. Using basic discrete mathematics, elementary real analysis and mathematical induction, we propose a self-contained derivation of bounds αn log_2 n + βn + γ in all cases. Independent of any programming language or pseudo-code, 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 us to actually discover constants, instead of simply checking them a posteriori.