Subject: Re: Question about the sort function
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 06 Oct 2007 04:18:41 -0500
Newsgroups: comp.lang.lisp
Message-ID: <jLednWhha-Rsz5ranZ2dnUVZ_jGdnZ2d@speakeasy.net>
skibud2 <mike.halloran@gmail.com> wrote:
+---------------
| If you have a list of words that are ALL UNIQUE, and you
| call sort with a predicate of string< like this:
|  (sort word-list #'string<)
+---------------

Others have addressed your question about the sort being stable,
but since no-one else mentioned it...  The bare expression:

    (sort word-list #'string<)

returns the sorted list, true, but does *not* leave the sorted
list in WORD-LIST. As it says in CLHS "Function SORT, STABLE-SORT":

    The sorting operation can be destructive in all cases.
    In the case of a vector argument, this is accomplished
    by permuting the elements in place. In the case of a list,
    the list is destructively reordered in the same manner
    as for nreverse.

This means that the following result is perfectly legal:

    > (let ((word-list (list :foo :bar :baz :quux)))
	(sort word-list #'string<)
	...[other stuff]...
	word-list)

    (:FOO :QUUX)
    > 

For this reason, if you want the sorted result you must save
it somehow, e.g.:

    > (let ((word-list (list :foo :bar :baz :quux))
	    result)
	(setf result (sort word-list #'string<))
	...[other stuff]...
	result)

    (:BAR :BAZ :FOO :QUUX)
    > 


-Rob

p.s. If you already knew this and simply didn't bother to show
the saving of the SORT result in your question/example, then my
apologies for the unnecessary tutorial. It's just that a SORT
outside of the context of a SETF [or as an argument to another
immediate function call] almost always signals a mistake.

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607