#
8566e629 |
|
09-Aug-2020 |
Michael Norrish <michael.norrish@data61.csiro.au> |
Allow Unicode lambda (λ, U+03BB) in src/ This is because writing things like (\(x,y). x + y) puts editor modes into strange states when they think the second left-parenthesis has been "escaped". Allowing a lambda to be used here gives us a chance to avoid confusing editors, and who wouldn't want that?
|
#
805c5015 |
|
26-May-2020 |
Andreas Lööw <AndreasLoow@users.noreply.github.com> |
Cleanup of append thms for SORTED
|
#
2ededc8d |
|
13-May-2019 |
Michael Norrish <Michael.Norrish@nicta.com.au> |
Implement new Definition syntax; use it in src/sort and Tutorial
|
#
18934f7c |
|
03-Dec-2018 |
Johannes Åman Pohjola <johannes.amanpohjola@data61.csiro.au> |
Reconcile store_thms with diverging names in db and val binding
|
#
aa23933d |
|
29-Jan-2016 |
Anthony Fox <anthony.fox@cl.cam.ac.uk> |
Opening lcsymtacs is no longer necessary.
|
#
84cc1436 |
|
13-Jan-2016 |
Michael Norrish <Michael.Norrish@nicta.com.au> |
All l/case short simp tacs use LET_ss + ARITH_ss This means that fs and rfs pick up LET_ss and ARITH_ss, making them indistinguishable from the 'l' versions.
|
#
98c7fd9e |
|
20-Sep-2015 |
Ramana Kumar <ramana@member.fsf.org> |
update mergesortTheory after redundant theorem removed
|
#
d2c33299 |
|
05-Nov-2014 |
Michael Norrish <michael.norrish@nicta.com.au> |
Remove some Unicode in src/
|
#
9243d31a |
|
05-Nov-2014 |
Michael Norrish <michael.norrish@nicta.com.au> |
Remove some trailing whitespace.
|
#
b04022f7 |
|
14-Aug-2014 |
Scott Owens <S.A.Owens@kent.ac.uk> |
A theory of mergesort Mergesort based on the algorithm used in OCaml. There are two versions. mergesort_tail uses a tail recursive merge (following OCaml) whereas mergesort uses a normal merge. Both are stable. Initial experiments show that mergesort outperforms QSORT and QSORT3 executing with EVAL. I ran each of the 4 sorts on 3 different lists of 10000 numbers. Call them SORTED (COUNT_LIST 10000), RAND32 (10000 random 32bit numbers), and RAND16 (10000 random 16bit numbers). NB, QSORT is not stable whereas QSORT3 is. mergesort mergesort_tail QSORT QSORT3 SORTED 10.9s 13.4s * * RAND32 27.6s 30.7s 33.8s 1m23s RAND16 18.2s 20.5s 21.4s 55.4s * QSORT and QSORT3 do not finish on the sorted input for (COUNT_LIST 500) they take 10.8s and 31.4s respectively. This is because quicksort exhibits its quadratic worst-case behaviour on already sorted inputs.
|