multi-way-merge as a tail recursive function in Scala

gistfile1.txt

trait Merge {
  def m_way_merge(out: List[Int], xs: List[List[Int]]): List[Int] = {
    val arrays = xs.remove(_ == Nil)
    if (arrays.isEmpty) {
      out
    } else {
      val idx: Int = arrays.findIndexOf((xs: List[Int]) => xs.head == arrays.map(_.head).sort(_ < _).head)
      m_way_merge(out ::: List(arrays(idx).head), arrays.slice(0, idx) ::: arrays.slice(idx + 1, arrays.length) ::: List(arrays(idx).tail))
    }
  }

  def m_way_merge(xs: List[List[Int]]): List[Int] = m_way_merge(Nil, xs)
}