Merge-Sort

; Takes two sorted lists
; Returns a sorted list with all elements from the first 2 lists
; (Works like the set union from a previous series)
(: merge-lists ((list-of number) (list-of number) -> (list-of number)))
(define merge-lists
  (lambda (xs ys)
    (cond
      [(empty? xs) ys]
      [(empty? ys) xs]
      [(< (first xs) (first ys))
       (cons (first xs) (merge-lists (rest xs) ys))]
      [else
       (cons (first ys) (merge-lists xs (rest ys)))])))

; Takes a list of numbers
; Returns a sorted list (using merge sort)
(: merge-sort ((list-of number) -> (list-of number)))
(define merge-sort
  (lambda (xs)
    (cond
      [(<= (length xs) 1) xs]
      [(= (length xs) 2)
       (merge-lists (list (first xs)) (rest xs))]
      [else
       (letrec ([x (ceiling (/ (length xs) 2))])
         (merge-lists (merge-sort (take xs x))
                      (merge-sort (drop xs x))))])))
; Takes a list and a number n
; Returns the first n elements from the list
(: take ((list-of %a) natural -> (list-of %a)))
(define take
  (lambda (l n)
    (cond [(empty? l) empty]
          [(= n 0) empty]
          [else (cons (first l) (take (rest l) (- n 1)))])))

; Takes a list and a number n
; Returns all but the first n elements from the list
(: drop ((list-of %a) natural -> (list-of %a)))
(define drop
  (lambda (l n)
    (cond [(empty? l) l]
          [(= n 0) l]
          [else (drop (rest l) (- n 1))])))