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

Re: Memory use of sort!

This page is part of the web mail archives of SRFI 95 from before July 7th, 2015. The new archives for SRFI 95 contain all messages, not just those from before July 7th, 2015.



Aubrey Jaffer skrev:
 | Date: Tue, 07 Nov 2006 13:52:04 +0100
 | From: =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <jensaxel@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 <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>

--
Jens Axel Søgaard