Scala general sort function does not work with arrays

Question

I am trying to write a sort function that will work with any sequence and returns the same sequence that is passed to this function. So I came up with this solution:

def qckSrt[U: Ordering, C <: Seq[U]](xs: C with SeqLike[U, C])
    (implicit bf: CanBuildFrom[C, U, C]): C = {
  val n = xs.length
  val b = bf()

  if (n <= 1) xs
  else {
    val p = xs.head
    val (left, right) = xs.tail partition { 
      implicitly[Ordering[U]].lteq(_, p)
    }
    b ++= qckSrt(left)
    b += p
    b ++= qckSrt(right)
    b.result()
  }
}

Thus, it works with lists, vectors, massive buffers ... But it does not work with a regular array:

scala> qckSrt(Array(1, 2, 6, 2, 5))
<console>:16: error: inferred type arguments [Int,Any] do not conform to method qckSrt type parameter bounds [U,C <: Seq[U]]
        qckSrt(Array(1, 2, 6, 2, 5))
        ^
<console>:16: error: type mismatch;
  found   : scala.collection.mutable.ArrayOps.ofInt
  required: C with scala.collection.SeqLike[U,C]
        qckSrt(Array(1, 2, 6, 2, 5))
               ^
<console>:16: error: No implicit Ordering defined for U.
        qckSrt(Array(1, 2, 6, 2, 5))

Is there a way to make this work also for arrays?

Answer 1

You can replace inheritance with implicit conversion. For arrays, this will use implicit conversion conversions, and for types that are already SeqLike, it will use subtype ( implicitly[C[U] <:< SeqLike[U, C[U]]]) proofs :

import scala.collection._
import scala.collection.generic.CanBuildFrom


def qckSrt[U: Ordering, C[_]](xs: C[U])(implicit
  bf: CanBuildFrom[C[U], U, C[U]],
  asSeq: C[U] => SeqLike[U, C[U]]
): C[U] = {
  val n = xs.length
  val b = bf()

  if (n <= 1) xs
  else {
    val p = xs.head
    val (left, right) = xs.tail partition {
      implicitly[Ordering[U]].lteq(_, p)
    }
    b ++= qckSrt(left)
    b += p
    b ++= qckSrt(right)
    b.result()
  }
}

"" C U .