Functional K-way merge (Merge k sorted sequences) I've implemented a functional k way-merge algorithm to merge k sorted sequences of any type T. I used scalaz's Heap since the Scala standard library does not provide an immutable heap. Any suggestions to make this more performant/concise/idiomatic are welcome :-

import scala.annotation.tailrec
import scalaz.Heap
import scalaz.Order.fromScalaOrdering   

def kWayMerge[T: Ordering](allSequences: IndexedSeq[IndexedSeq[T]]): IndexedSeq[T] = {    
    case class PQNode(elem: T, indexInList: Int, indexOfList: Int)

    implicit val pqOrdering = fromScalaOrdering(Ordering.by[PQNode, T](_.elem))
    val pqNodes = allSequences.zipWithIndex.map {
      case (list, indexOfList) =&gt;
        list.zipWithIndex.map { case (a, b) =&gt; PQNode(a, b, indexOfList) }
    }

    @tailrec
    def loop(priorityQueue: Heap[PQNode], sortedList: IndexedSeq[T]): IndexedSeq[T] = {
      if (priorityQueue.isEmpty) sortedList
      else {
        val minNode = priorityQueue.minimum
        val newPq = priorityQueue.deleteMin
        val finalPQ = pqNodes(minNode.indexOfList).lift(minNode.indexInList + 1).fold(newPq)(newPq.insert(_))
        loop(finalPQ, sortedList :+ minNode.elem)
      }
    }

    val priorityQueue = pqNodes.foldLeft(Heap.Empty[PQNode])((heap, list) =&gt; heap.insert(list(0)))
    loop(priorityQueue, IndexedSeq.empty[T])
  }
I've been thinking about this question literally for weeks.

It always seemed like this implementation suffers from "hammer syndrome" - if you have a really good hammer, you want to think every problem is a nail. Functional coding is a great tool for many things, but in this case, it has a problem.

The reason why algorithms use mutable rather than immutable heaps is asymptotic performance. In a heap sort, a mutable heap gives you log n time per element, but an immutable heap would have n time per element (because you have to copy the entire heap of size n in addition to doing the re-heap with time log n).

Similarly, a k-way merge implemented with immutable heaps will run in nk time, rather than n log k time. That's fine if k is small but even with modest sized k, will become a significant performance hit.

It would have been helpful if test cases had been included so that reviewers could take a look at performance numbers with various possible changes.

The code itself looks fine to me. The fact that nobody wrote a review could mean that most people who read the question came to the same conclusion. As an academic exercise, I say, good job. In the long run, I doubt such an algorithm is genuinely useful except in truly unusual circumstances