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

;; constructor: 
;; construct a new list from f and r
;; Number LON --> LON
;; (cons f r) 

;; predicate -- is the given datum a cons? (of any kind of data)
;; Any --> Boolean
;; (cons? a-list)

;; selector for the first element of the list
;; LON --> Number
;; (first a-list)

;; selector for the remainder of the list
;; LON --> LON
;; (rest a-list)

;; produce a sorted list of numbers from this list of numbers
;; LON --> [LON (sorted)]
(define (sort a-list)
  (cond
    [(empty? a-list) empty]
    [else (insert (sort (rest a-list)) (first a-list))]))

;; Template
;; ... (empty? a-list) ...                          -- Boolean
;; ... (cons? a-list) ...                           -- Boolean
;;     ... (first a-list) ...                       -- Number
;;     ... (rest a-list) ...                        -- LON

;;     ... (sort (rest a-list)) ...                 -- [LON (sorted)]
;;     ... (insert (sort (rest a-list)) Number) ... -- [LON (sorted)]

;; produce a sorted list by inserting a number into a sorted list
;; [LON (sorted)] Number --> [LON (sorted)]
(define (insert s-list num)
  (cond 
    [(empty? s-list) (cons num s-list)]
    [else
     (cond
       [(< num (first s-list)) (cons num s-list)]
       [else (cons (first s-list) (insert (rest s-list) num))])]))

;; Template
;; ... (empty? a-list) ...                    -- Boolean
;; ... (cons? a-list) ...                     -- Boolean
;;     ... (first a-list) ...                 -- Number
;;     ... (rest a-list) ...                  -- [LON (sorted)]

;;     ... (insert (rest a-list)) Number) ... -- [LON (sorted)]


;; examples
(equal? empty (sort empty))
(equal? (list 2 4 6 8) (sort (list 4 8 2 6)))

(equal? (list 2 4 6 8) (insert (list 4 6 8) 2))
(equal? (list 2 4 6 8) (insert (list 2 6 8) 4))
(equal? (list 2 4 6 8) (insert (list 2 4 6) 8))