1. A bargain for mergesorts (functional pearl) -- How to prove your mergesort correct and stable, almost for free
- Author
-
Cohen, Cyril and Sakaguchi, Kazuhiko
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Data Structures and Algorithms ,Computer Science - Programming Languages - Abstract
We present a novel characterization of stable mergesort functions using relational parametricity, and show that it implies the correctness of mergesort. As a result, one can prove the correctness of several variations of mergesort (e.g., top-down, bottom-up, tail-recursive, non-tail-recursive, smooth, and non-smooth mergesorts) by proving the characterization property for each variation. To further motivate this work, we show a performance trade-off between tail-recursive and non-tail-recursive mergesorts that (1) the former in call-by-value evaluation avoids using up stack space and is efficient and (2) the latter in call-by-need evaluation is an optimal incremental sort, meaning that it performs only $\mathcal{O}(n + k \log k)$ comparisons to compute the least (or greatest) $k$ items of a list of length $n$. Thanks to our characterization and the parametricity translation, we deduced the correctness results, including stability, of various implementations of mergesort for lists, including highly optimized ones, in the Coq proof assistant., Comment: The supplementary material is available at https://github.com/pi8027/stablesort
- Published
- 2024