マージソート

Scheme 30分プログラム

30分プログラム、その802。
3年前のマージソート(http://d.hatena.ne.jp/mzp/20070421/msort)をまたやってみた。

使い方

gosh> (msort '(3 1 2))
(1 2 3)

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
(use util.match)
(use srfi-1)

(define (merge xs ys)
  (match (cons xs ys)
	 [(() . ()) ()]
	 [(xs . ()) xs]
	 [(() . ys) ys]
	 [((x . xs) . (y . ys))
	  (if (< x y)
	      (cons x (merge  xs        (cons y ys)))
	      (cons y (merge (cons x xs) ys)))]))

(define (split xs)
  (receive (a b)  (partition cadr
			     (zip xs (circular-list #t #f)))
	   (values (map car a) (map car b))))

(define (msort xs)
  (if (or (null? xs) (null? (cdr xs)))
      xs
      (receive (ys zs) (split xs)
	       (merge (msort ys) (msort zs)))))

参考