Subversion Repositories scarts

;;; "sort.scm" Defines: sorted?, merge, merge!, sort, sort!

;;; Author : Richard A. O'Keefe (based on Prolog code by D.H.D.Warren)

;;; Modified for scheme library: Aubrey Jaffer 19 Sept. 1991

;;; (sorted? sequence less?)

;;; such that for all 1 <= i <= m,

;;;     (not (less? (list-ref list i) (list-ref list (- i 1)))).

;;; (merge a b less?)

;;; takes two lists a and b such that (sorted? a less?) and (sorted? b less?)

;;; interleaved so that (sorted? (merge a b less?) less?).

;;; Note:  this does _not_ accept vectors.  See below.

;; The loop handles the merging of non-empty lists.  It has

;; been written this way to save testing and car/cdring.

;; x <= y

;;; (merge! a b less?)

;;; takes two sorted lists a and b and smashes their cdr fields to form a

;;; single sorted list including the elements of both.

;;; Note:  this does _not_ accept vectors.

;; (car a) <= (car b)

; (car a) <= (car b)

;;; (sort! sequence less?)

;;; sorts the list or vector sequence destructively.  It uses a version

;;; of merge-sort invented, to the best of my knowledge, by David H. D.

;;; Warren, and first used in the DEC-10 Prolog system.  R. A. O'Keefe

;;; adapted it to work destructively in Scheme.

;; otherwise, assume it is a list

;;; (sort sequence less?)

;;; that the result of append is always "newly allocated" except for

;;; sharing structure with "the last argument", so (append x '()) ought

;;; to be a standard way of copying a list x.

;;; eof