;; ListOfNumber (LoN) is one of
;; -- empty
;; -- (cons Number LoN)

;; A Sorted LoN (SLoN) is one of
;; -- empty
;; -- (cons Number SLoN)
;; where in the case (cons n r) where n is a Number and r is SLoN
;; it is true that n < all items in SLoN

;; TEMPLATE
#|
(define (f lon)
  (cond 
    [(empty? lon) ...]
    [(cons? lon) ... (first lon)...
                 .. (f (rest lon)) ...]))
|#

;; insert: Number SLon -> SLon
;; inserts n in order
(define (insert n lon) 
    (cond 
    [(empty? lon) (list n)]
    [(cons? lon) (cond
                   [(< n (first lon)) (cons n lon)]
                   [else (cons (first lon)
                               (insert n (rest lon)))])]))


;; Examples
'insert-examples
(equal? (insert 1 empty) '(1))
(equal? (insert 1 '(2 3)) '(1 2 3))
(equal? (insert 3 '(1 2)) '(1 2 3))
(equal? (insert 2 '(1 3)) '(1 2 3))


;; sort: LoN -> SLoN
;; sorts the list from least to greatest
(define (sort lon)
    (cond 
    [(empty? lon) empty]
    [(cons? lon) (insert (first lon)
                         (sort (rest lon)))]))

;; Examples
'sort-examples
(equal? (sort empty) empty)
(equal? (sort '(1)) '(1))
(equal? (sort '(2 1)) '(1 2))