;; (listof X)[size=n] -> (listof X)[size=n/2]]
;; returns the first half of a list, if that list is odd in length
;; with length n, it will return n/2+1 items
(define (firsthalf lst)
  (local ((define (loop n l)
            (cond
              [(>= n (/ (length lst) 2)) empty]
              [else (cons (first l) (loop (add1 n) (rest l)))])))
    (loop 0 lst)))

;; Examples
(equal? (firsthalf empty) empty)
(equal? (firsthalf (list 1 2 3 4)) (list 1 2))
(equal? (firsthalf (list 1 2 3 4 5)) (list 1 2 3))

;; (listof X)[size=n] -> (listof X)[size=n/2]]
;; returns the second half of a list, if that list is odd in length
;; with length n, it will return n/2 items
(define (secondhalf lst)
  (local ((define (loop n l)
            (cond
              [(empty? l) empty]
              [(< n (/ (length lst) 2)) (loop (add1 n) (rest l))]
              [else (cons (first l) (loop (add1 n) (rest l)))])))
    (loop 0 lst)))

;; Examples
(equal? (secondhalf empty) empty)
(equal? (secondhalf (list 1 2 3 4)) (list 3 4))
(equal? (secondhalf (list 1 2 3 4 5)) (list 4 5))

;; merge: (sorted listof Number) (sorted listof Number) -> (sorted listof Number)
;; returns a sorted list consisting of the items of both input lists
;; note: the input lists must be sorted
(define (merge l1 l2)
  (cond
    [(empty? l1) l2]
    [(empty? l2) l1]
    [(< (first l1) (first l2)) (cons (first l1) (merge (rest l1) l2))]
    [else                      (cons (first l2) (merge l1 (rest l2)))]))

;; Examples
(equal? (merge empty empty) empty)
(equal? (merge empty (list 1 2)) (list 1 2))
(equal? (merge (list 1 2) empty) (list 1 2))
(equal? (merge (list 1 3) (list 2 4)) (list 1 2 3 4))



;; mergesort: (listof Number) -> (listof Number)
;; returns a sorted version of the input list
(define (mergesort lon)
  (cond
    [(<= (length lon) 1) lon]
    [else (merge (mergesort (firsthalf lon))
                 (mergesort (secondhalf lon)))]))

;; Examples
(equal? (mergesort empty) empty)
(equal? (mergesort (list 4 3 2 1)) (list 1 2 3 4)