Next: Topological Sort, Previous: Chapter Ordering, Up: Sorting and Searching [Contents][Index]
(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.
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).
Merges two sorted lists, returning a freshly allocated list as its result.
Merges two sorted lists, re-using the pairs of list1 and list2 to build the result. The result will be either list1 or list2.
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
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
Next: Topological Sort, Previous: Chapter Ordering, Up: Sorting and Searching [Contents][Index]