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.

This won't be as efficient as the code mentioned in the question. Sorry to miss the important part. Updated the question — sidgate, Aug 10 '16 at 07:17

leetwinski · Accepted Answer · 2016-08-10T08:00:35.433

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)

score 5 · Answer 2 · answered Aug 10 '16 at 08:06

I think this is really easiest expressed simply with tail-recursion:

def merge(x: List[Int], y: List[Int]): List[Int] = {
  def loop(xss: List[Int], yss: List[Int], acc: List[Int]) = (xss, yss) match {
    case (x :: xs, y :: ys) if x < y => loop(xs, yss, x :: acc)
    case (_, y :: ys) => loop(xss, ys, y :: acc)
    case (x :: xs, Nil) => loop(xs, Nil, x :: acc)
    case (Nil, Nil) => acc.reverse
  }

  loop(x, y, Nil)
}

score 3 · Answer 3 · answered Aug 10 '16 at 08:20

Something like this, perhaps? Can probably be done prettier, but the general idea should work.

public static <T extends Comparable<T>> Stream<T> foldSorted(Stream<T> left, Stream<T> right) {
    Iterator<T> leftIterator = left.iterator();
    Iterator<T> rightIterator = right.iterator();

    Iterator<T> iterator = new Iterator<T>() {
        private T nextLeft = getNextLeft();
        private T nextRight = getNextRight();

        private T getNextLeft() {
            return leftIterator.hasNext() ? leftIterator.next():null;
        }

        private T getNextRight() {
            return rightIterator.hasNext() ? rightIterator.next():null;
        }

        @Override
        public boolean hasNext() {
            return nextLeft != null || nextRight != null;
        }

        @Override
        public T next() {
            T result = null;

            if(nextLeft != null) {
                if(nextRight != null) {
                    if(nextLeft.compareTo(nextRight) < 0) {
                        result = nextLeft;
                        nextLeft = getNextLeft();
                    } else {
                        result = nextRight;
                        nextRight = getNextRight();
                    }
                } else {
                    result = nextLeft;
                    nextLeft = getNextLeft();
                }
            } else {
                result = nextRight;
                nextRight = getNextRight();
            }

            return result;
        }
    };

    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, Spliterator.ORDERED), false);
}

Now, you can do:

@Test
public void verifyFoldSorted() {
    List<Integer> result = StreamUtils.foldSorted(Stream.of(1, 5, 7, 9), Stream.of(2, 5)).collect(Collectors.toList());
    assertEquals(Arrays.asList(1, 2, 5, 5, 7, 9), result);

    result = StreamUtils.foldSorted(Stream.of(8, 10), Stream.of(1, 2, 7, 9)).collect(Collectors.toList());
    assertEquals(Arrays.asList(1, 2, 7, 8, 9, 10), result);
}

Thanks. This seems to be the right solution for Java. Just one problem, the values from primitive array gets boxed/ unboxed. I am trying out `OfInt` iterator, will update — sidgate, Aug 10 '16 at 09:18

Konstantin Yovkov · Answer 4 · 2016-08-10T07:14:37.437

2

You could wrap the arrays you want to merge into a two-dimensional array and then do:

IntStream result = Arrays.stream(new int[][]{{3, 2, 1}, {5, 2, 4}})
                         .flatMapToInt(Arrays::stream)
                         .sorted();

Note that it doesn't really matter if the arrays are pre-sorted or not.

edited Aug 10 '16 at 07:14

answered Aug 10 '16 at 07:12

Konstantin Yovkov

62,134
8
100
147

Thanks for the answer. This gives the expected output, but won't be as efficient as the loop. – sidgate Aug 10 '16 at 07:14

jwvh · Answer 5 · 2016-08-10T09:24:40.590

Scala

If you want a lazy evaluation, i.e. each element sorted and retrieved only as needed, then one approach is turn your Arrays into Iterators.

class ArrayMerger[A:Ordering](arrA:Array[A], arrB:Array[A]) extends Iterator[A] {
  import math.Ordering.Implicits._
  private val a: BufferedIterator[A] = arrA.toIterator.buffered
  private val b: BufferedIterator[A] = arrB.toIterator.buffered

  override def hasNext: Boolean = a.hasNext || b.hasNext
  override def next(): A =
    if      (!a.hasNext) b.next()
    else if (!b.hasNext) a.next()
    else if (a.head < b.head) a.next() else b.next()
}

val am = new ArrayMerger(Array('a','c','t','y'),Array('b','w','z'))//Iterator[Char]
am.toArray  // Array(a, b, c, t, w, y, z)  <-- iterator consumed

A Stream also has lazy evaluation but it can be indexed as well.

val am = new ArrayMerger(Array(43, 78), Array(2, 36, 77, 87, 99)).toStream
am(1) // 36
am(4) // 78
am(6) // 99  <-- only now have all elements been evaluated

score 2 · Answer 6 · answered Aug 10 '16 at 12:12

The tail-recursive solution by @leetwinski works well, but it isn't lazy. Here's a lazy solution in Clojure:

(defn merge-sorted [pred coll1 coll2]
  (lazy-seq
   (if (some empty? [coll1 coll2])
     (concat coll1 coll2)
     (let [[head1 & tail1] coll1
           [head2 & tail2] coll2]
       (if (pred head1 head2)
         (cons head1 (merge-sorted pred tail1 coll2))
         (cons head2 (merge-sorted pred coll1 tail2)))))))

Example:

(letfn [(multiples [x]
          (iterate (partial +' x) x))]
  (take 10 (merge-sorted < (multiples 2) (multiples 3))))
;;=> (2 3 4 6 6 8 9 10 12 12)

score 0 · Answer 7 · answered Aug 10 '16 at 07:15

0

You can also use folding to accomplish it in scala,

val l1 = List(1,2,3,4)
val l2 = List(1, 2, 3, 4, -1, 2, 3, 5, 6, 7, 8)

val merged = l2.foldLeft(l1)((acc,i) => acc :+ i).sorted

answered Aug 10 '16 at 07:15

Fatih Donmez

4,319
3
33
45

if performance isn't a concern, this version could also be `(l1 ++ l2).sorted`, but if performance matters, @gzm0 's answer above should be faster. – handler Aug 11 '16 at 03:28
question before edits was all about functional approach to solve problem. This one is another example only :) – Fatih Donmez Aug 11 '16 at 03:48

user_3380739 · Answer 8 · 2023-01-20T06:06:46.170

0

It can be done with third-party library abacus-common:

int[] a = { 1, 3, 5, 7 };
int[] b = { 2, 4, 6 };
int[] c = IntStream.merge(a, b, (v1, v2) -> v1 < v2 ? Nth.FIRST : Nth.SECOND).toArray();
N.println(c); // output: [1, 2, 3, 4, 5, 6, 7]

edited Jan 20 '23 at 06:06

answered Jan 10 '17 at 18:31

user_3380739

1
14
14

Merge two arrays using functional style

8 Answers8