[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Memory use of sort!



 | Date: Tue, 14 Nov 2006 15:01:56 +0100
 | From: =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <jensaxel@soegaard.net>
 | 
 | ...
 | 
 |  > | Date: Sun, 12 Nov 2006 16:06:59 -0800
 |  > | From: Per Bothner <per@bothner.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.