Efficient Mergesort

Christian Sternagel 📧

November 9, 2011

Abstract

We provide a formalization of the mergesort algorithm as used in GHC's Data.List module, proving correctness and stability. Furthermore, experimental data suggests that generated (Haskell-)code for this algorithm is much faster than for previous algorithms available in the Isabelle distribution.
BSD License

Change history

November 20, 2020

Additional theory Natural_Mergesort that developes an efficient mergesort algorithm without key-functions for educational purposes.

September 19, 2018

Theory Efficient_Mergesort replaces theory Efficient_Sort but keeping the old name Efficient_Sort.

September 17, 2018

Added theory Efficient_Mergesort that works exclusively with the mutual induction schemas generated by the function package.

October 24, 2012

Added reference to journal article.

Topics

Theories of Efficient-Mergesort