Formal comment #47 (enhancement)

Add (sort) and (vector-sort!) procedures
Reported by:	Jason Orendorff

Component:	other
Version:	5.91

The utility of a standard sort routine seems beyond doubt. It seems
almost every non-joke language provides one.

For the sake of putting forth a realistic proposal, I suggest adopting
(only) the non-stable functional list-sort and the non-stable
four-parameter in-place vector-sort! from SRFI-32. But I don't really
care what the committee chooses. Any standard sorting facility would
be better than none.

I try to anticipate possible objections:

- "No one sort algorithm is good enough for all cases." I carelessly
  estimate that a standard sort can be good enough for >99% of the use
  cases--without inconveniencing the <1% of users who need a
  specialized sort for whatever reason.

- "But sort can be implemented efficiently using other features of
  Scheme--unlike, say, hash tables." I don't know how true that is,
  but assuming it's completely true, I consider (sort) a convenience
  feature on par with (map), (filter), (for-each), and (cond).

- "People are already complaining that the spec is too long." I'm
  sympathetic to this view. In response I can only offer my own
  opinion, of course; but I think a simple sort is more important,
  provides more bang for the complexity buck, than any number of other
  things in the 5.91 spec: continuing to support delay/force, for
  example. It would be consistent to add sorting procedures while
  cutting other features to make room.

- "But if we add these we'll have to add list-sort! and vector-sort
  and stable-list-sort and vector-merge and..." I don't think
  so. Certainly there's no need to add them all right
  now. Non-destructively making a sorted copy of a list and
  destructively sorting a range of a vector in-place probably cover
  the overwhelming majority of real-world use cases. Sure, this is
  slightly asymmetric--if the use cases of lists and vectors were
  totally isomorphic, we wouldn't have them both.

- "But implementors..." Eh, they can handle it.

RESPONSE:

The R6RS should definitely provide sorting routines in one
of its standard libraries.

The comment proposes two procedures from a SRFI that was
withdrawn several years ago.  Both are non-stable, and one
is destructive.

As can be seen by reading section 23 of the draft R6RS,
higher-order procedures that perform side effects create
problems.  To reduce these problems, and to provide the
most useful sorting routines with the simplest API, the
the R6RS will provide (at least) the following procedures:

(list-sort proc list)
(vector-sort proc vec)

For both procedures, the first argument must be a predicate
that accepts any two elements of the list or vec and returns
a boolean indicating whether its first argument is strictly
less than its second.  This predicate should not have any
side effects.

The list-sort and vector-sort procedures perform a stable
sort of the list or vec, without changing the given list or
vec in any way.  The list-sort procedure returns a list, and
vector-sort returns a vector.  The results may be eq? to the
arguments when the arguments are already sorted, and the
result of list-sort may share structure with a tail of the
original list.  The sorting algorithm performs O(n lg n)
calls to the predicate, and all arguments passed to the
predicate are elements of the list or vector being sorted,
but the pairing of arguments and the sequencing of calls to
the predicate are not specified.

Notes:

Placing the procedure first is the convention established
for R5RS and previous reports.

Using "less than" is consistent with Common Lisp and with
SRFI 1.

The effect of a destructive sort on a subvector can be
obtained by copying the subvector into a fresh vector,
performing a non-destructive sort, and copying the result
back into the original subvector.  The copying would not
change the asymptotic complexity of the overall sort, is
unlikely to add much to the sort's constant factors, and
has much cleaner semantics than a destructive sort in place.