; has-zero-or-one-elements? : list-of-X -> boolean
(define has-zero-or-one-elements?
  (lambda (lon)
    (or (empty? lon) (empty? (rest lon)))))

; take : list-of-X number -> list-of-X
; returns a list containing the first n elements of the argument
(define take
  (lambda (lon n)
    (cond [(zero? n)   empty]
	  [(cons? lon) (cons (first lon) (take (rest lon) (sub1 n)))]
	  [else        (error "List too short.")])))

; drop: list-of-X number -> list-of-X
; return a list containing all but the first n elements of the argument
(define drop
  (lambda (lon n)
    (cond [(zero? n)   lon]
	  [(cons? lon) (drop (rest lon) (sub1 n))]
	  [else        (error "List too short.")])))

; merge : list-of-number * list-of-number -> list-of-number
; merges two sorted (non-descending) lists into one sorted list
(define merge
  (lambda (lon1 lon2)
    (cond [(empty? lon1) lon2]
	  [(empty? lon2) lon1]
	  [else          (if (< (first lon1) (first lon2))
			     (cons (first lon1) (merge (rest lon1) lon2))
			     (cons (first lon2) (merge lon1 (rest lon2))))])))

; mergesort : list-of-number -> list-of-number
; returns the sorted (non-descending) version of the argument
(define mergesort
  (lambda (lon)
    (if (has-zero-or-one-elements? lon)
	lon
	(local [(define len (length lon))
		(define len-half (truncate (/ len 2)))]
	  (merge (mergesort (take lon len-half))
		 (mergesort (drop lon len-half)))))))