;;; (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.

(define (sort! seq less?)
    (define (step n)
        (cond
            ((> n 2)
                (let* ((j (quotient n 2))
                       (a (step j))
                       (k (- n j))
                       (b (step k)))
                    (merge! a b less?)))
            ((= n 2)
                (let ((x (car seq))
                      (y (cadr seq))
                      (p seq))
                    (set! seq (cddr seq))
                    (if (less? y x) (begin
                        (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
                '()) ))
    (if (vector? seq)
        (let ((n (vector-length seq))
              (vec seq))
          (set! seq (vector->list seq))
          (do ((p (step n) (cdr p))
               (i 0 (+ i 1)))
              ((null? p) vec)
            (vector-set! vec i (car p)) ))
        ;; otherwise, assume it is a list
        (step (length seq)) ))

(define (shuffle l random)
  (let ((len (length l)))
    (map cdr
         (sort! (map (lambda (x) (cons (random len) x)) l)
                (lambda (x y) (< (car x) (car y)))))))