(define revappend
  (lambda (x y)
    (if (null? x) y
	(revappend (cdr x) (cons (car x) y)))))

(define reverse
  (lambda (x)
    (revappend x '())))

(define iter
  (lambda (f x)
    (if (null? x) '() (begin (f (car x)) (iter f (cdr x))))))

(define print-digit (lambda (x) (write-char x)))

(define digits
  (lambda (x cs)
    (if (= x 0) cs
	(let ((y (/ x 10))
	      (d (- x (* y 10)))
	      (c (integer->char (+ d (char->integer (string-ref "0" 0))))))
	  (digits y (cons c cs))))))

(define print-int
  (lambda (x)
    (cond ((= x 0) (write "0"))
	  ((< x 0) (begin (write "-") (print-int (- 0 x))))
	  (else (iter print-digit (digits x '()))))))

(define print-pair
  (lambda (x)
    (begin 
      (write "(")
      (print-value (car x))
      (write " . ")
      (print-value (cdr x))
      (write ")"))))

(define print-string
  (lambda (x)
    (begin
      (write "\"")
      (write x)
      (write "\""))))

(define print-char
  (lambda (x)
    (begin
      (write "'")
      (write-char x)
      (write "'"))))

(define print-value
  (lambda (x)
    (cond ((null? x) (write "'()"))
	  ((integer? x) (print-int x))
	  ((pair? x) (print-pair x))
	  ((char? x) (print-char x))
	  ((string? x) (print-string x))
	  ((input-port? x) (write "#indesc"))
	  ((output-port? x) (write "#outdesc"))
	  ((procedure? x) (write "#fn"))
	  (else (write "#t")))))

(define print-newline (lambda () (write-char (integer->char 10))))
    
(define print-val (lambda (x) (print-value x) (print-newline)))

(define generate
  (lambda (i l)
    (if (= i 0) l (generate (- i 1) (cons i l)))))

(define split
  (lambda (l1 l2 l3)
    (if (null? l1) (cons l2 l3)
	(split (cdr l1) l3 (cons (car l1) l2)))))

(define merge
  (lambda (l1 l2 l3)
    (cond ((null? l1) (revappend l2 l3))
	  ((null? l2) (revappend l1 l3))
	  (else
	   (let ((x1 (car l1))
		 (x2 (car l2)))
	     (if (< x1 x2) 
		 (merge (cdr l1) l2 (cons x1 l3))
		 (merge l1 (cdr l2) (cons x2 l3))))))))

(define mergesort
  (lambda (l)
    (cond ((null? l) l)
	  ((null? (cdr l)) l)
	  (else
	   (let ((p (split l '() '())))
	     (reverse (merge (mergesort (car p)) 
			     (mergesort (cdr p)) '())))))))

(define y (generate 100 '()))

(define z (print-val (mergesort y)))
