diff options
| author |  herbelin <herbelin@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-12-04 10:34:25 +0000 |
|---|---|---|
| committer | herbelin <herbelin@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-12-04 10:34:25 +0000 |
| commit | aea34fdc7caec6faf9cf54e70ae33631357ec0f1 (patch) | |
| tree | 91fecbca9d5d065a589902b7a150c8a59996db3e /theories/Sorting | |
| parent | b62f4058b45f8fab24885b030b85ed1ca328445c (diff) | |
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
Diffstat (limited to 'theories/Sorting')
| -rw-r--r-- | theories/Sorting/Mergesort.v | 3 |
1 files changed, 2 insertions, 1 deletions
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 |