;; a ListOfNumber is one of
;;   empty
;;   (cons Number ListOfNumber)

;; sort:  ListOfNumber -> ListOfNumber
;; consumes a list of numbers and produces a list with
;; the numbers sorted in ascending order
(define (sort alon)
  (cond [(empty? alon) empty]
        [(cons? alon) (insert (first alon) (sort (rest alon)))]))

(check-expect (sort empty) empty)
(check-expect (sort (cons 3 (cons 1 (cons 2 (cons 14 empty)))))
              (cons 1 (cons 2 (cons 3 (cons 14 empty)))))

;; insert: Number ListOfNumber (sorted) -> ListOfNumber (sorted)
;; consumes a number and a sorted list of numbers, and produces a list
;; with the given number inserted into the proper place in the sorted list
(define (insert anum aslon)
  (cond [(empty? aslon) (cons anum empty)]
        [(cons? aslon) (if (< anum (first aslon))
                           (cons anum aslon)
                           (cons (first aslon) (insert anum (rest aslon))))]))

(check-expect (insert 5 empty) (cons 5 empty))
(check-expect (insert -2 (cons 1 (cons 5 (cons 9 empty))))
              (cons -2 (cons 1 (cons 5 (cons 9 empty)))))
(check-expect (insert 12 (cons 2 (cons 9 empty)))
              (cons 2 (cons 9 (cons 12 empty))))
(check-expect (insert 3 (cons 1 (cons 2 (cons 14 empty))))
              (cons 1 (cons 2 (cons 3 (cons 14 empty)))))