From aea34fdc7caec6faf9cf54e70ae33631357ec0f1 Mon Sep 17 00:00:00 2001 From: herbelin Date: Sat, 4 Dec 2010 10:34:25 +0000 Subject: Fixing coqdoc pretty-printing of a table in Mergesort. Incidentally, this fixes #2441 (even though some other problem was involved too that r16673 might have solved). git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13677 85f007b7-540e-0410-9357-904b9bb8a0f7 --- theories/Sorting/Mergesort.v | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'theories/Sorting') diff --git a/theories/Sorting/Mergesort.v b/theories/Sorting/Mergesort.v index 0d06cf671..7124cd536 100644 --- a/theories/Sorting/Mergesort.v +++ b/theories/Sorting/Mergesort.v @@ -59,6 +59,7 @@ Fixpoint merge l1 l2 := For instance, here is how [6;2;3;1;5] is sorted: +<< operation stack list iter_merge [] [6;2;3;1;5] = append_list_to_stack [ + [6]] [2;3;1;5] @@ -75,7 +76,7 @@ Fixpoint merge l1 l2 := = append_list_to_stack [[1;2;3;6];; + [5]] [] -> merge_stack [[1;2;3;6];;[5]] = [1;2;3;5;6] - +>> The complexity of the algorithm is n*log n, since there are 2^(p-1) mergings to do of length 2, 2^(p-2) of length 4, ..., 2^0 of length 2^p for a list of length 2^p. The algorithm does not need -- cgit v1.2.3