How can I make my isSorted function faster?
The problem is simply that your two solutions are not equivalent. For example, you would probably not use Array, but barring that, a direct translation of the Java code to Scala would be:

def isSorted[A](items: Array[A], cond: (A, A) =&gt; Boolean): Boolean = {
    for (i &lt;- 1 until items.length if !cond(items(i - 1), items(i))) {
      return false
    }
    return true
}


However, using an Array in Scala is a bit uncommon, and one would rather use Seq instead. Especially, a LinearSeq promises an efficient tail operation but slow indexing, this is reversed for an IndexedSeq.

@tailrec // remind the compiler that the recursion can be eliminated
def isSorted[A](items: LinearSeq[A], cond: (A, A) =&gt; Boolean): Boolean = items match {
  case Seq()     =&gt; true  // you forgot to handle empty input!
  case Seq(_)    =&gt; true 
  case x :: tail =&gt; cond(x, tail.head) &amp;&amp; isSorted(tail, cond)
}


But in this specific case, destructuring is actually silly: The isSorted test should male sense for any iterable (let's hope that it terminates, but that isn't our problem). It doesn't actually matter that much here that we can't do much destructuring for a general trait like Iterable. This here is a fairly elegant solution, but I wouldn't make any bets about performance.

def isSorted[A](items: Iterable[A], cond: (A, A) =&gt; Boolean): Boolean =
  items.isEmpty || (items zip items.tail forall (pair =&gt; cond(pair._1, pair._2)))


The zip method joins two lists pairwise: items = Seq(1, 2, 3, 4) would then produce ((1, 2), (2, 3), (3, 4)).

I am not sure whether any of these solutions would actually be faster – it's to be expected that Scala is a bit slower than Java, but the difference for a careful implementation should not be as large as in your question.



Style notes:


Always annotate tail recursive functions with @tailrec (from the scala.annotation package). This will either perform a tail call optimization or produce an error if the compiler is unable to do so.
When specifying the type of a variable, put a space after the :, but not before: name: Type. (source)
Invoke methods by using ., except when the method is an operator or takes a function as parameter – items.tail instead of items tail (source)
In general, the spacing around your operators is inconsistent. A comma should always be followed by a space, and binary operators like = or &lt; should have a space on either side. (source)