[r6rs-discuss] [Formal] Add (sort) and (vector-sort!) procedures

[Jed Davis]

On Fri, Oct 13, 2006 at 01:24:30AM +0200, Marcin 'Qrczak' Kowalczyk wrote:
> Aubrey Jaffer <ajaffer at clearmethods.com> writes:
> 
> >  | The key should be extracted exactly once for each element.
> >
> > Because there are potentially more than O(N) comparisons, keys are
> > potentially accessed more than once.  So the sort routines would need
> > to allocate O(N) storage to hold the keys to meet this requirement.
> 
> If an implementation extracts keys once, I have a choice: for a fast
> key extraction function I can pass a comparator which extracts keys
> on each comparison to save some memory, and for a slow key extraction
> I can rely on the variant with a key extractor doing the appropriate
> thing.

And if the key-extract function is impure, this can affect the results
and not just the run time -- e.g., sorting a list of files by time of
last modification, where the get-key calls Unix stat(2) or equivalent,
would yield Bad Stuff if a file were modified during the sort.

-- 
(let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map
((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l))))))  (lambda
(f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l))
(C k)))))))    '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline)))))