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) =>
        list.zipWithIndex.map { case (a, b) => PQNode(a, b, indexOfList) }

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.