Re: Memory use of sort! Jens Axel Søgaard 14 Nov 2006 14:01 UTC

Aubrey Jaffer skrev:
>  | Date: Tue, 07 Nov 2006 13:52:04 +0100
>  | From: =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <xxxxxx@soegaard.net>
>  |
>  | The specification of sort! reads:
>  |
>  |    Function: sort! sequence less?
>  |    Function: sort! sequence less? key
>  |
>  |        Returns list, array, vector, or string sequence which has
>  |    been mutated to order its elements according to less?. Given
>  |    valid arguments, it is always the case that:
>  |
>  |        (sorted? (sort! sequence less?) less?) => #t
>  |
>  | Would be possible to add that the sorting is in-place?
>
> Just before the specification of SORTED? is:
>
>   The `!' variants sort in place; sort! returns its sequence argument.

I missed that.

 > | Date: Sun, 12 Nov 2006 16:06:59 -0800
 > | From: Per Bothner <xxxxxx@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>

--
Jens Axel Søgaard