diff options
Diffstat (limited to 'theories/Sorting/Mergesort.v')
| -rw-r--r-- | theories/Sorting/Mergesort.v | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/theories/Sorting/Mergesort.v b/theories/Sorting/Mergesort.v index e576db2b..04de1bfc 100644 --- a/theories/Sorting/Mergesort.v +++ b/theories/Sorting/Mergesort.v @@ -6,7 +6,7 @@ (* * GNU Lesser General Public License Version 2.1 *) (************************************************************************) -(*i $Id: Mergesort.v 13323 2010-07-24 15:57:30Z herbelin $ i*) +(*i $Id: Mergesort.v 13678 2010-12-04 10:34:28Z herbelin $ i*) (** A modular implementation of mergesort (the complexity is O(n.log n) in the length of the list) *) @@ -61,6 +61,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] @@ -77,7 +78,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 |