;;pass merge-sort a list, and it will sort it
(define (merge-sort lst)
  (if (list? lst)
    ;;if a list is passed, send it to the divide function
    (divide lst)
    (error "Not a list")
  )
)

;;divide takes a list, and either divides it into two lists
;;and merges them
;;or, if the list is length 0, 1, or 2, returns the sorted version of the list
(define (divide lst)
  (cond
    ((null? lst) lst) ;;empty list is just returned
    ((= (length lst) 1) lst) ;;list of length 1 is also returned
    ((= (length lst) 2) ;;list of length 2 is sorted and returned
      (if (> (car lst)(cadr lst))
        (list (cadr lst)(car lst))
        lst
      )
    )
    (else
      ;;long list is divided into two parts, which are recursively divided
      ;;and then merged together
      (merge
        '()
        (divide 
          (reverse
            (list-tail
              (reverse lst)
              (inexact->exact (floor (/ (length lst) 2)))
            )
          )
        )
        (divide
          (list-tail
            lst
            (inexact->exact (ceiling (/ (length lst) 2)))
          )
        )
      )
    )
  )
)

;;merge takes three lists
;;pass the first as empty, and the other two are the lists to merge
;;it will then merge the two lists together in sorted order
(define (merge lst1 lst2 lst3)
  (cond
    ;;if the two lists are null, just return the first list
    ((and (null? lst2)(null? lst3)) lst1)
    ;;if one of the lists is null, return the first list and the other
    ;;list appended together
    ((null? lst2) (append lst1 lst3))
    ((null? lst3) (append lst1 lst2))
    (else
      ;;figure out which list has a smaller element at the begining
      ;;put that on the first list, take it off the list it came from, and just
      ;;pass the other list as it is
      (if (< (car lst2)(car lst3))
        (merge
          (append lst1 (list (car lst2)))
          (cdr lst2)
          lst3
        )
        (merge
          (append lst1 (list (car lst3)))
          lst2
          (cdr lst3)
        )
      )
    )
  )
)