How can I define a method that takes an Ordered[T] Array in Scala?

Question

I'm building some basic algorithms in Scala (following Cormen's book) to refresh my mind on the subject and I'm building the insertion sort algorithm. Doing it like this, it works correctly:

class InsertionSort extends Sort {

def sort ( items : Array[Int] ) : Unit = {

    if ( items.length < 2 ) {
        throw new IllegalArgumentException( "Array must be bigger than 1" )
    }

    1.until( items.length ).foreach( ( currentIndex ) => {

        val key = items(currentIndex)

        var loopIndex = currentIndex - 1

        while ( loopIndex > -1 && items(loopIndex) > key ) {

            items.update( loopIndex + 1, items(loopIndex) )

            loopIndex -= 1
        }

        items.update( loopIndex + 1, key )

    } )

}

}    

But this is for Int only and I would like to use generics and Ordered[A] so I could sort any type that is ordered. When I change the signature to be like this:

def sort( items : Array[Ordered[_]] ) : Unit

The following spec doesn't compile:

"sort correctly with merge sort" in {

  val items = Array[RichInt](5, 2, 4, 6, 1, 3)

  insertionSort.sort( items )

  items.toList === Array[RichInt]( 1, 2, 3, 4, 5, 6 ).toList

}

And the compiler error is:

Type mismatch, expected: Array[Ordered[_]], actual Array[RichInt]

But isn't RichInt an Ordered[RichInt]? How should I define this method signature in a way that it would accept any Ordered object?

EDIT

In case anyone is interested, the final source is available here.

Answer 1

Actually RichInt is not an Ordered[RichInt] but an Ordered[Int]. However scala.runtime.RichInt <: Ordered[_], but class Array is invariant in type T so Array[RichInt] is not an Array[Ordered[_]].

scala> def f[T <% Ordered[T]](arr: Array[T]) = { arr(0) < arr(1) }
f: [T](arr: Array[T])(implicit evidence$1: T => Ordered[T])Boolean

scala> f(Array(1,2,3))
res2: Boolean = true

scala>