cl:sort!   scheme

;;; (cl:sort! sequence less?)
;;; sorts the list, array, or string 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.
;@
(define (cl:sort! seq less?)
  (define (step n)
    (cond ((> n 2)
     (let* ((j (quotient n 2))
      (a (step j))
      (k (- n j))
      (b (step k)))
       (cl:merge! a b less?)))
    ((= n 2)
     (let ((x (car seq))
     (y (cadr seq))
     (p seq))
       (set! seq (cddr seq))
       (cond ((less? y x)
        (set-car! p y)
        (set-car! (cdr p) x)))
       (set-cdr! (cdr p) '())
       p))
    ((= n 1)
     (let ((p seq))
       (set! seq (cdr seq))
       (set-cdr! p '())
       p))
    (else '())))
   (step (length seq)))