Next: , Previous: Chapter Ordering, Up: Sorting and Searching


7.2.4 Sorting

(require 'sort) or (require 'srfi-95) [by Richard A. O'Keefe, 1991]

I am providing this source code with no restrictions at all on its use (but please retain D.H.D.Warren's credit for the original idea).

The code of merge and merge! could have been quite a bit simpler, but they have been coded to reduce the amount of work done per iteration. (For example, we only have one null? test per iteration.)

I gave serious consideration to producing Common-LISP-compatible functions. However, Common LISP's sort is our sort! (well, in fact Common LISP's stable-sort is our sort!; merge sort is fast as well as stable!) so adapting CL code to Scheme takes a bit of work anyway. I did, however, appeal to CL to determine the order of the arguments.

The standard functions <, >, char<?, char>?, char-ci<?, char-ci>?, string<?, string>?, string-ci<?, and string-ci>? are suitable for use as comparison functions. Think of (less? x y) as saying when x must not precede y.

[Addendum by Aubrey Jaffer, 2006]

These procedures are stable when called with predicates which return #f when applied to identical arguments.

The sorted?, merge, and merge! procedures consume asymptotic time and space no larger than O(N), where N is the sum of the lengths of the sequence arguments. The sort and sort! procedures consume asymptotic time and space no larger than O(N*log(N)), where N is the length of the sequence argument.

All five functions take an optional key argument corresponding to a CL-style ‘&key’ argument. A less? predicate with a key argument behaves like:

     (lambda (x y) (less? (key x) (key y)))

All five functions will call the key argument at most once per element.

The ‘!’ variants sort in place; sort! returns its sequence argument.

— Function: sorted? sequence less?
— Function: sorted? sequence less? key

Returns #t when the sequence argument is in non-decreasing order according to less? (that is, there is no adjacent pair ... x y ... for which (less? y x)).

Returns #f when the sequence contains at least one out-of-order pair. It is an error if the sequence is not a list or array (including vectors and strings).

— Function: merge list1 list2 less?
— Function: merge list1 list2 less? key

Merges two sorted lists, returning a freshly allocated list as its result.

— Function: merge! list1 list2 less?
— Function: merge! list1 list2 less? key

Merges two sorted lists, re-using the pairs of list1 and list2 to build the result. The result will be either list1 or list2.

— Function: sort sequence less?
— Function: sort sequence less? key

Accepts a list or array (including vectors and strings) for sequence; and returns a completely new sequence which is sorted according to less?. The returned sequence is the same type as the argument sequence. Given valid arguments, it is always the case that:

          (sorted? (sort sequence less?) less?) ⇒ #t
— Function: sort! sequence less?
— Function: sort! sequence less? key

Returns list, array, vector, or string sequence which has been mutated to order its elements according to less?. Given valid arguments, it is always the case that:

          (sorted? (sort! sequence less?) less?) ⇒ #t