merge.clj

(def xs (sort (repeatedly 30 #(rand-int 20))))

(def ys (sort (repeatedly 25 #(rand-int 20))))

(defn merge-sorted-seqs
  [xs ys]
  (lazy-seq (cond
             (empty? xs) (seq ys)
             (empty? ys) (seq xs)
             :else (let [x (first xs) y (first ys)]
                     (if (<= x y)
                       (cons x (merge-sorted-seqs (rest xs) ys))
                       (cons y (merge-sorted-seqs xs (rest ys))))))))

;; If you then want to process equal elements together:

(partition-by identity (merge-sorted-seqs xs ys))