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(n2) bound on the number of calls to the comparison procedure, and the omission of the stability requirement.