But things look pretty good there as we only need to get Olin's code to
replace the sorting code in big/sort.scm.
Take http://shivers.org/~shivers/tmp/sort.tgz
It will get you going for now
- It has a better replacement for the old buggy T code by Nix.
- Also heapsort, insertion sort, vector merge sort, binary search, sort?,
list merge & delete-neighbor-duplicates
- Plus top-level cover functions with non-algo-specific names & S48 module
files with type decls
- Plus doc (draft SRFI spec)
- Plus testing code
BUT...
- no quick sort of any kind
- so you will need to rip the quicksort entries out of the package file & doc
- and this code is all going to change, in fact
Why?
I am writing a paper on my sort algo. This has caused me, in the last
few weeks, to (1) come up with some new, more sophisticated algos and
(2) benchmark a slew of std algos. I am doing all this in SML. When the
smoke clears, I will port the winners to Scheme. But the paper has to
be finished first.
As for qsort, I have three different versions written. If you want to
sort through them, I will send you the code.
As always, the code is voluminously commented.
Run with this code for this release. The all-singing all-dancing version
for the next release. (In brief, the algorithmic upgrades will be
- merge naturally builds its result backwards. You can adjust the algo
to handle this -- the next merge reverses the reversed list, etc.
This reduces consing by a factor of 2 and is a *huge* speed win.
- top-down variants of the natural sorts give better merge trees
- List merge sorts can spot decreasing as well as increasing runs,
and can force runs to be of length at least three, eliminating
bottom layer of merge tree.
- Loops can be "rotated" to eliminate recursive calls on bottom ply of
call tree.)
- vector merge sort can use insert sort to force runs up to a minimum
length of 6, eliminating bottom layers of merge tree.)
If you don't like the terms in the copyright on the files, change them.
-Olin
|