I, too, am wondering why the Scala implementation didn't fare as well as the Java implementation.

Offtopic: I'm not an expert on functional programming (just getting my feet wet; forgive me for being so naive), but after reading Scala By Example I have this nagging feeling that a functional implementation of an algorithm might actually run slower than an imperative implementation of the same algorithm. I mean, you're copying data all around the place, creating new instances of objects instead of modifying them in place, using a ton of recursion everywhere. Could anyone offer some perspective on this?