IteratorUtil.scala

object IteratorUtil {
  def merge[_T](aIterators: Iterator[_T]*)(implicit aOrdering: Ordering[_T]): Iterator[_T] = {
    def nextOrNone(aIterator: Iterator[_T]): Option[_T] = if (aIterator.hasNext) Some(aIterator.next) else None
    implicit object ElementOrdering extends Ordering[(Int, Option[_T], Iterator[_T])] {
      override def compare(x: (Int, Option[_T], Iterator[_T]), y: (Int, Option[_T], Iterator[_T])) = (x, y) match {
        case ((_, None, _), (_, None, _)) => 0
        case ((_, None, _), (_, _, _)) => 1
        case ((_, _, _), (_, None, _)) => -1
        case ((_, Some(tLeft), _), (_, Some(tRight), _)) => aOrdering.compare(tLeft, tRight)
      }
    }

    val tArray = aIterators.zipWithIndex.map { case (tIterator, i) => (i, nextOrNone(tIterator), tIterator) }.toArray

    Iterator.continually({
      val (tIndex, tValue, tIterator) = tArray.min
      tArray(tIndex) = (tIndex, nextOrNone(tIterator), tIterator)
      tValue
    }).takeWhile(_ != None).map(_.get)
  }

    def main(aArgs: Array[String]): Unit = {
      val tList1 = List(1,4,5,7,8)
      val tList2 = List(1,2,3,7,10)
      val tList3 = List(1,2,3,7,9)

      val tMerged = merge(tList1.iterator, tList2.iterator, tList3.iterator)
      tMerged.foreach(println)

      println(merge(tList1.iterator, tList2.iterator, tList3.iterator).toList == (tList1 ++ tList2 ++ tList3).sorted)
    }
}