;;Die Funktion merge verbindet 2 sortierte listen zu einer sortierten liste.
;;[merge]:(list-of-numbers list-of-numbers)->(list-of-numbers)
(check-expect (merge (list 1 2 3 4) (list 1 2 3 4)) (list 1 1 2 2 3 3 4 4))
(check-expect (merge (list 3 4) (list 1 2 8)) (list 1 2 3 4 8))
(check-expect (merge empty (list 1 2 8)) (list 1 2 8))
(check-expect (merge (list 1 2 8) empty) (list 1 2 8))

(define merge-one-element
  (lambda [z lon2]
    (cond
      [(> z (first lon2)) (append (list (first lon2)) (merge-one-element z (rest lon2)))]
      [(<= z (first lon2)) (cons z lon2)])))

(define merge
  (lambda [lon1 lon2]
    (cond
      [(and (empty? lon1) (empty? lon2)) '()]
      [(empty? lon1) lon2]
      [(empty? lon2) lon1]
      [else (merge (rest lon1) (merge-one-element (first lon1) lon2))])))