freenode/#sicl - IRC Chatlog
Search
16:39:28
beach
jcowan: Though if shka__ is doing what I think he is, then the purpose is to implement a very efficient stable sort for vectors. Merge sort is known to be be stable and very efficient, but the standard description of it requires O(n) extra space.
16:40:08
beach
jcowan: But there are some recent articles on how to implement merging, and therefor merge sort, in O(1) additional space.
16:42:05
beach
jcowan: I would personally like to attempt the trick we did in our article on how to process lists from the end, i.e. use SOME stack space if it is available. Then I believe one could achieve a very fast merge sort on vectors with a performance that degrades smoothly when stack space is scarce.
18:35:53
shka_
jcowan: i am literally doing what is described in "A simple shuffle-based stable in-place merge algorithm" by Mehmet Emin Dalkilic
18:38:13
shka_
i think that once i have in-place merge ready, actual merge-sort should be rather easy to implement
18:46:17
shka_
jcowan: I thing that it would be the best to implement several sorting algorithms and then compare them against each other
18:47:48
shka_
i am doing this particular one not only because it seems to be good, but also because of the coolness factor
19:55:59
jcowan
my main contribution will have to be to point to https://github.com/scheme-requests-for-implementation/srfi-132/tree/master/sorting
19:56:23
jcowan
which is admittedly in Scheme, but should be completely readable modulo inserting the occasional `funcall` mentally.