Re: the sort function in lisp (destructive)

On Jan 6, 2:23 pm, Kent M Pitman <pit...@xxxxxxxxxxx> wrote:
"John Thingstad" <jpth...@xxxxxxxxx> writes:
På Sun, 06 Jan 2008 17:38:04 +0100, skrev Rainer Joswig <jos...@xxxxxxx>:

Another alternative would be a SORT that does not reorder
the CONS cells, ...

In fact looking at the source for Corman Lisp I discovered that it
reads  the CAR into a vector, sorts that, and then puts the values
back in the  CAR's in sorted order.

This might have been done for other reasons than avoiding side-effect.
For example, to avoid having two different sort algorithms, or even
because it didn't occur to him how to write the algorithm without
doing indexed access.

Another possible reason is to avoid a certain kind of degenerate cache/
paging behavior. If you sort a long, randomly ordered list by
changing cdr's, merely traversing the resulting list cells makes for a
terrible memory access pattern.

.

Relevant Pages

  • Re: a question about sort!
    ... > take a lot of memory if we use copy-list in a repetitive way)? ... - SORT will return a list that is a sorted version of the list you ... Copying will create as many new cons cells as there are ... elements in the list so you don't want to do it for no reason. ...
    (comp.lang.lisp)
  • Re: How to improve this sort?
    ... I have written an ascending sort routine for floats. ... This is as bad as sort algorithms get. ... As far as comparing two floats with a unique ordering -- that is guaranteed. ...
    (comp.lang.c)
  • Re: C Qsort algorithm - limit on number of objects to sort
    ... Dan wrote: ... >> ints?) ... then sort algorithms and implementations are a dime a dozen. ...
    (comp.programming)
  • Re: How to improve this sort?
    ... I have written an ascending sort routine for floats. ... comparisions with previously sorted elements are made. ... This is as bad as sort algorithms get. ...
    (comp.lang.c)
  • Re: Data structure
    ... sort algorithms which exploit the structure of the key space cannot ... If keys are integers or floating point ... strings that might differ only near the tail end, ...
    (comp.programming)