Merge two arrays using functional style

Question

I was looking at one of the questions How to merge two sorted arrays, and trying hard to convert the solution using Java 8 streams. But still no success. Actually, nothing useful that I can share here.

There has to be a way to handle such loops using indexes in functional programming. How would this been done in other languages, like Scala, Clojure, without changing the time complexity? May be then I can just try to copy it in Java.

Edit: The code mentioned the question is the most efficient, and I don't want to compromise on it.

Answer 1

in fact there is the same approach everywhere: you recur over two collections, adding least of collections' heads to the result, and recurring with the rest, until one of collections (or both) is empty. In clojure:

(defn merge-sorted [pred coll1 coll2]
  (loop [coll1 coll1 coll2 coll2 res []]
    (cond (or (empty? coll1) (empty? coll2)) (concat res coll1 coll2)
          (pred (first coll1) (first coll2)) (recur (rest coll1)
                                                    coll2
                                                    (conj res (first coll1)))
          :else (recur coll1 (rest coll2) (conj res (first coll2))))))

user> (merge-sorted < [1 3 5 6 7 8 9 40 50] [1 2 5 10 100])
(1 1 2 3 5 5 6 7 8 9 10 40 50 100)