Sorting an array in-place in Scala

Question

I tried this:

implicit class ArrayExtensions[A](a: Array[A]) {
  /**
   * Sort a slice [from, until) of this array
   */
  def sort(from: Int, until: Int)(implicit cmp: Ordering[A]) = java.util.Arrays.sort(a, from, until, cmp)
}

But, I think I am hitting a bug in the compiler:

[error]  found   : Array[A]
[error]  required: Array[? with Object]
[error] Note: A >: ? with Object, but class Array is invariant in type T.
[error] You may wish to investigate a wildcard type such as `_ >: ? with Object`. (SLS 3.2.10)
[error]     def sort(from: Int, until: Int)(implicit cmp: Ordering[A]) = java.util.Arrays.sort(a, from, until, cmp)

How do I get around this?

I think JVM can be a tag. I believe Java should not be a tag. — mubeen
– mubeen, Commented Mar 4, 2016 at 5:20
What is the problem with calling java.util.Arrays.sort directly? — kostya
– kostya, Commented Mar 4, 2016 at 8:38
@kostya: I just posted the compile error I get when I call java.util.Arrays — pathikrit
– pathikrit, Commented Mar 4, 2016 at 8:40
I mean, if you have val a: Array[Int], you can just call Arrays.sort(a, from, until) and it will just work. Why do you want to introduce ArrayExtensions? — kostya
– kostya, Commented Mar 4, 2016 at 8:42
I managed to make it work by copying scala.util.Sorting.quickSort code, replacing Array with mutable.IndexedSeq in it, and sorting with quicksort(a.view(from, until)). See gist.github.com/kolmar/5b891c6058b16757525b I'm not sure why Scala doesn't provide any built-in quickSort method for sorting a mutable sequence in place. — Kolmar
– Kolmar, Commented Mar 4, 2016 at 10:16

Joe Pallas · Accepted Answer · 2016-03-04 06:37:21Z

3

The answer to your question is right there in the bug you cited: "Java generic array cannot be used with Scala value types". As the bug says, the real problem is that the error message isn't too helpful. The problem is that you have no constraints on the type of A, but not all Scala types can be used as Java generic type parameters, only reference types can. Try this:

implicit class ArrayExtensions[A <: AnyRef](a: Array[A]) {
    /**
     * Sort a slice [from, until) of this array
     */
    def sort(from: Int, until: Int)(implicit cmp: Ordering[A]) = java.util.Arrays.sort(a, from, until, cmp)
}

AnyRef corresponds to Java Object, while Any includes Scala types that are not Java objects (like Int).

answered Mar 4, 2016 at 6:37

Joe Pallas

2,1551 gold badge15 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Teliatko Over a year ago

For completeness link to Scala issue issues.scala-lang.org/plugins/servlet/mobile#issue/si-5783. It's not bug per se, just not enough clear error message.

Teliatko Over a year ago

@pathikrit it can't work for Array[Int] per definition. You are calling generic Java method, which is still generic in Java sense, i.e. only for Object sub-classes, which obviously int in Java isn't. On Scala side, the Java constraint is interpreted as being a sub-class of AnyRef, while AnyRef ~= Object, which again Scala Int isn't. Search for specialized annotation to have an special case for Int. See scala-notes.org/2011/04/specializing-for-primitive-types

pathikrit · Accepted Answer · 2016-03-04 05:24:04Z

1

So, far I have gotten around by doing this:

a.slice(from, until).sorted.copyToArray(a, from)

But, this is not ideal as it requires two extra traversals.

answered Mar 4, 2016 at 5:24

pathikrit

33.7k39 gold badges154 silver badges230 bronze badges

Collectives™ on Stack Overflow

Sorting an array in-place in Scala

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related