Re: Memory use of sort! Aubrey Jaffer 12 Nov 2006 23:56 UTC

 | 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?  That is
 | guarantee, that no (or very little) extra memory is allocated
 | during the sorting process.

I originally had language to limit allocation of pairs, but it
required all sorts of caveats about the stack and other potential uses
of pairs.  I find no such language in R5RS; does any SRFI limit pair
allocation?

As W. Clinger points out, some things must be left to the
quality-of-implementation.