Next: , Previous: , Up: Sorting and Searching   [Contents][Index]

#### 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`.

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
```

Next: , Previous: , Up: Sorting and Searching   [Contents][Index]