Articles

A didactic analysis of merge sort

Published:
2013-12-01
Author
View
Keywords
License

Copyright (c) 2013 Christian Rinderknecht

Creative Commons License

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.