How can I make my isSorted function faster? I made an isSorted function in Scala and Java as well and when I measured the time of functions' run I saw that the Scala version was very slow. It ran about 3.2 sec for 10000 Int but java version just ran about 10 ms!

How can I make faster my Scala version?

Scala:

def main(args: Array[String]) ={
    println(isSorted(getArray, (x:Int,y:Int) =&gt; x&lt;y ))
}
def isSorted[A](items : Array[A], cond: (A,A) =&gt; Boolean) : Boolean = items match{
  case Array(_) =&gt; true 
  case Array(x,y) =&gt;cond(x,y)
  case Array(_*) =&gt; cond(items(0),items(1)) &amp;&amp; isSorted(items tail,cond)
}


Java:

public static void main(String... args){
    Sorter sorter=new Sorter();
    System.out.println(sorter.isSorted(sorter.getList(),new Comparator&lt;Integer&gt;() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }));
}
public &lt;A&gt; boolean isSorted(List&lt;A&gt; items, Comparator&lt;A&gt; cond){
    for(int i=1;i&lt;items.size();i++){
            if(cond.compare(items.get(i-1), items.get(i)) &lt; 0){
                return false;
            }
        }
    return true;
}


Any suggestions?

I would like to use Scala, but this bad performance scared me!
Can I keep Scala's syntactic sugar?
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)