;; Question 3

;; code from lectures
;; merge: (listof num) (listof num) -> (listof num)
;; merges list1 and list2 provided both are sorted in
;;  ascending order
(define (merge list1 list2)
  (cond
    [(and (empty? list1) (empty? list2)) empty]
    [(and (empty? list1) (cons? list2)) list2]
    [(and (cons? list1) (empty? list2)) list1]
    [(and (cons? list1) (cons? list2))
     (cond
       [(< (first list1) (first list2))
        (cons (first list1) (merge (rest list1) list2))]
       [ else
         (cons (first list2) (merge list1 (rest list2)))])]))

;; helper functions
(define (make-singles alon)
  (cond [(empty? alon) empty]
        [else (cons (list (first alon)) (make-singles (rest alon)))]))

(define (chop n alol)
  (cond [(empty? alol) empty]
        [(equal? n (first alol)) (rest alol)]
        [else (chop n (rest alol))]))

(define (merge-all-neighbors alol)
  (cond [(empty? alol) empty]
        [(empty? (rest alol)) (list (first alol))]
        [else (cons (cond [(< (first (first alol)) (first (second alol)))
                           (append (first alol) (second alol))]
                          [else (append (second alol) (first alol))])
                    (merge-all-neighbors (chop (second alol) alol)))]))