(defn conj-not-empty [coll item]
  (if-not item coll (conj coll item)))

(defn mergesorted
  ([collections]
   (mergesorted collections <))

  ([collections comparator]
   (mergesorted collections comparator (transient [])))

  ([collections comparator sorted]
   (if (<= (count collections) 1)
     (concat (persistent! sorted) (first collections))

     (let [[with-smallest & anothers] (sort-by first comparator collections)
           [smallest & tail] with-smallest
           collections (conj-not-empty anothers tail)]
       (recur collections comparator (conj! sorted smallest))))))

(mergesorted [[0] [1 5] [2 6] [7] [3] [4] [3] [-1] [8] [5]]) ; (-1 0 1 2 3 3 4 5 5 6 7 8)