`(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?(keyx) (keyy)))

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`

— Function:

Returns

`#t`

when the sequence argument is in non-decreasing order according toless?(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`

— Function:

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

— Function: **merge!**` list1 list2 less?`

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

— Function:

Merges two sorted lists, re-using the pairs of

list1andlist2to build the result. The result will be eitherlist1orlist2.

— Function: **sort**` sequence less?`

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

— Function:

Accepts a list or array (including vectors and strings) for

sequence; and returns a completely new sequence which is sorted according toless?. The returned sequence is the same type as the argumentsequence. Given valid arguments, it is always the case that:(sorted? (sortsequenceless?)less?) ⇒ #t