[ create a new paste ] login | about

Link: http://codepad.org/hqwyVHRh    [ raw code | output | fork ]

Scheme, pasted on May 21:
(define split
  (lambda (ls)
    (letrec ((split-h (lambda (ls ls1 ls2)
                        (cond
                          ((or (null? ls) (null? (cdr ls)))
                           (cons (reverse ls2) ls1))
                          (else (split-h (cddr ls)
                                  (cdr ls1) (cons (car ls1) ls2)))))))
      (split-h ls ls '()))))

(define (merge lst1 lst2)
  (if (null? lst1)
      lst2
    (if (null? lst2)
	lst1
      (if (< (car lst1) (car lst2))
	  (cons (car lst1) (merge (cdr lst1) lst2))
	(cons (car lst2) (merge lst1 (cdr lst2)))))))

(define mergesort
  (lambda (pred ls)
    (cond
      ((null? ls) ls)
      ((null? (cdr ls)) ls)
      (else (let ((splits (split ls))) 
              (merge (mergesort pred (car splits)) (mergesort pred (cdr splits))))))))

(display (mergesort '() '(3 5 1 4 2)))


Output:
1
(1 2 3 4 5)


Create a new paste based on this one


Comments: