home *** CD-ROM | disk | FTP | other *** search
/ BMUG PD-ROM A / PD-ROM A.iso / Programming / Programming Languages / Gambit LISP / sort.scm < prev    next >
Encoding:
Text File  |  1991-01-28  |  683 b   |  30 lines  |  [TEXT/gamI]
  1. ; Sort using mergesort
  2. ;
  3. ; (sort '(6 2 8 4 1) <) ==> (1 2 4 6 8)
  4.  
  5. (define (sort l <?)
  6.  
  7.   (define (mergesort l)
  8.  
  9.     (define (merge l1 l2)
  10.       (cond ((null? l1) l2)
  11.             ((null? l2) l1)
  12.             (else
  13.              (let ((e1 (car l1)) (e2 (car l2)))
  14.                (if (<? e1 e2)
  15.                  (cons e1 (merge (cdr l1) l2))
  16.                  (cons e2 (merge l1 (cdr l2))))))))
  17.  
  18.     (define (split l)
  19.       (if (or (null? l) (null? (cdr l)))
  20.         l
  21.         (cons (car l) (split (cddr l)))))
  22.  
  23.     (if (or (null? l) (null? (cdr l)))
  24.       l
  25.       (let* ((l1 (mergesort (split l)))
  26.              (l2 (mergesort (split (cdr l)))))
  27.         (merge l1 l2))))
  28.  
  29.   (mergesort l))
  30.