;; Data definition
;;
;; A List-of-Numbers is one of
;;  - empty
;;  - (cons Number List-of-Numbers)

;; List-of-Numbers examples
empty
(cons 3 (cons 6 (cons 8 (cons 10 empty))))
(cons 2 (cons 1 empty))
(cons 7 (cons 5 (cons 8 (cons 1 empty))))

;; sort : List-of-Numbers -> List-of-Numbers
;; sorts the list in ascending order

#| Template for sort
(define (sort a-lon)
  (cond
    [(empty? a-lon) ... ]
    [(cons? a-lon) ... (first a-lon) ...
                   ... (sort (rest a-lon)) ... ]))
|#
 
(define (sort a-lon)
  (cond
    [(empty? a-lon) empty]
    [else (insert (first a-lon) (sort (rest a-lon)))]))
  
;; insert : Number List-of-Numbers -> List-of-Numbers
;; inserts a new number into an already sorted list

#| Template for insert
(define (insert n a-lon)
  (cond
    [(empty? a-lon) ... ]
    [(cons? a-lon) ... (first a-lon) ...
                   ... (insert n (rest-alon)) ... ]))
|#

(define (insert n a-lon)
  (cond
    [(empty? a-lon) (cons n empty)]
    [else (cond
            [(<= n (first a-lon)) (cons n a-lon)]
            [else (cons (first a-lon) (insert n (rest a-lon)))])]))

;; Examples/tests for insert
(insert 25 empty) "should be" (cons 25 empty)
(insert 7 (cons 3 (cons 6 (cons 8 (cons 10 empty))))) "should be"
(cons 3 (cons 6 (cons 7 (cons 8 (cons 10 empty)))))

;; Examples/tests for sort
(sort (cons 2 (cons 1 empty))) "should be" (cons 1 (cons 2 empty))
(sort (cons 7 (cons 5 (cons 8 (cons 1 empty))))) "should be"
(cons 1 (cons 5 (cons 7 (cons 8 empty))))