Schemeでマージソート

やってみた。

(define merge-sort
  (lambda (lis)
    (if (= (length lis) 1)
      lis
      (let* ((n (div (length lis) 2))
             (left (take lis n))
             (right (drop lis n)))
        (merge (merge-sort left) (merge-sort right))))))

(define merge
  (lambda (lis1 lis2)
    (let loop ((l1 lis1) (l2 lis2) (l0 '()))
      (cond ((and (null? l1) (null? l2)) (reverse l0))
            ((null? l1) (loop l1 (cdr l2) (cons (car l2) l0)))
            ((null? l2) (loop (cdr l1) l2 (cons (car l1) l0)))
            ((< (car l1) (car l2)) (loop (cdr l1) l2 (cons (car l1) l0)))
            (else (loop l1 (cdr l2) (cons (car l2) l0)))))))

(print (merge-sort '(5 1 7 6 8 2 9 3 4)))

実行結果：

^o^ > gosh merge-sort.scm
(1 2 3 4 5 6 7 8 9)