So I’ve picked up a new book, Introduction to Algorithms, 3rd ed. and I’ve decided to try implementing some of them as a practice using Scheme, specifically I’m using a vanilla install of Chez Scheme.

(define merge-sort
  (lambda (l A L R sw)
	(cond
	  ((and (null? L) (null? l)) (append A R))
	  ((and (null? R) (null? l)) (append A L))
	  (else
		(cond 
		  ((null? l)
		   (cond
			 ((and (null? A) (or (= sw 1) (= sw 0)))
			  (merge-sort 
				l 
				A 
				(merge-sort L '() '() '() 0) 
				(merge-sort R '() '() '() 0) 
				-1))
			 (else
		   		(if (<= (car L) (car R))
			 		(merge-sort 
					  l 
					  (append A (list (car L))) 
					  (cdr L) 
					  R 
					  sw)
			 		(merge-sort 
					  l 
					  (append A (list (car R))) 
					  L 
					  (cdr R) 
					  sw)))))
		  (else
			(if (= sw 0)
			  (merge-sort 
				(cdr l) 
				A 
				(append L (list (car l))) 
				R 
				1)
			  (merge-sort 
				(cdr l) 
				A 
				L 
				(append R (list (car l))) 
				0))))))))

(merge-sort '(85 6 43 33 21 9 1 3 22 84 85) '() '() '() 0)