Re: Memory use of sort! Aubrey Jaffer 25 Nov 2006 15:39 UTC
| Date: Tue, 14 Nov 2006 15:01:56 +0100 | From: =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <firstname.lastname@example.org> | | ... | | > | Date: Sun, 12 Nov 2006 16:06:59 -0800 | > | From: Per Bothner <email@example.com> | > | | > | Aubrey Jaffer wrote: | > | > http://en.wikipedia.org/wiki/Sorting_algorithm has a table of | > | > properties for sort algorithms. "In-place merge sort" is shown as | > | > stable, O(n log(n)) time, and using no additional memory. | | I meant "using no additional memory", when I wrote "in-place". | | > | "In-place merge sort" works well for lists. Is there an in-place | > | version for vectors? | | > I think | > | http://citeseer.ist.psu.edu/rd/0%2C472101%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/24817/http:zSzzSzstaff.cs.utu.fizSzstaffzSztomi.pasanenzSzPS_of_pubszSzmergesort_NJC.pdf/katajainen96practical.pdf | > gives one. | | > I am saturated with work now. Anyone up for coding it? | | Can't this be used? | | <http://svn.plt-scheme.org/plt/trunk/collects/srfi/32/vmsort.scm> That link is bad. But vmsort.scm from scheme48 and srfi-32 both copy the initial vector -- so they use additional memory.