diff options
| -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 |