Efficient Mergesort

Christian Sternagel 📧

November 9, 2011

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

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.

License

BSD License

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

Session Efficient-Mergesort

Used by

Cite

× 
@article{Efficient-Mergesort-AFP,
  author  = {Christian Sternagel},
  title   = {Efficient Mergesort},
  journal = {Archive of Formal Proofs},
  month   = {November},
  year    = {2011},
  note    = {\url{https://isa-afp.org/entries/Efficient-Mergesort.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest

Older releases: