(require 'sort) or
[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! 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
I gave serious consideration to producing Common-LISP-compatible
functions. However, Common LISP’s
sort is our
(well, in fact Common LISP’s
stable-sort is our
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
string-ci>? are suitable for use as
comparison functions. Think of
(less? x y) as saying when
x must not precede
[Addendum by Aubrey Jaffer, 2006]
These procedures are stable when called with predicates which return
#f when applied to identical arguments.
merge! procedures consume
asymptotic time and space no larger than O(N), where N is the
sum of the lengths of the sequence arguments.
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
#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)).
#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