Sorting

The procedures of the `(rnrs sorting (6))` library provide simple
interfaces to sorting algorithms useful to many programs. In
particular, `list-sort` and `vector-sort` guarantee stable
sorting using *O*(*n* lg *n*) calls to the comparison procedure.
Straightforward implementations of merge sort [7] have
the desired properties. Note that, at least with merge sort,
stability carries no significant implementation or performance burden.

The choice of “strictly less than” for the comparison relation is consistent with the most common choice of existing Scheme libraries for sorting. Moreover, using a procedure returning three possible values (for less than, equal, and greater than) instead of a boolean comparison procedure would make calling the sorting procedures less convenient, with no discernible performance advantage.

The specification of the `vector-sort!` procedure is meant to
allow an implementation using quicksort [17], hence the *O*(*n*^{2})
bound on the number of calls to the comparison procedure, and the
omission of the stability requirement.