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?(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* 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

Next: Topological Sort, Previous: Chapter Ordering, Up: Sorting and Searching [Contents][Index]