事实上，各地的做法都是一样的：循环遍历两个集合，将最少的集合头添加到结果中，然后循环遍历其余的集合，直到其中一个集合（或两个集合）为空。

(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)

我认为这是最简单的表达简单的尾部递归：

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)
}

也许是这样的？也许可以做得更漂亮，但总体思路应该可行。

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);
}

现在，您可以执行以下操作：

@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);
}

您可以将想要合并的数组“ Package ”成二维数组，然后执行以下操作：

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

注意，数组是否预先排序并不重要。

斯卡拉

如果您想要一个惰性求值，即每个元素只在需要时排序和检索，那么一种方法是将Array s转换为Iterator s。

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

Stream也有惰性求值，但它也可以被索引。

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

@leetwinski的尾部递归解决方案运行良好，但它并不懒惰，下面是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)))))))

示例：

(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)

你也可以在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

可以使用第三方库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]