Clean implementation of sorts for scala.util.Sorting.

Removed code based on Sun JDK sorts and implemented new (basic) sorts from
scratch.  Deferred to Java Arrays.sort whenever practical.  Behavior of
`scala.util.Sorting` should be unchanged, but changed documentation to
specify when the Java methods are being used (as they're typically very fast).

A JUnit test is provided.

Performance is important for sorts.  Everything is better with this patch,
though it could be better yet, as described below.

Below are sort times (in microseconds, SEM < 5%) for various 1024-element
arrays of small case classes that compare on an int field (quickSort), or
int arrays that use custom ordering (stableSort).  Note: "degenerate"
means there are only 16 values possible, so there are lots of ties.
Times are all with fresh data (no re-using cache from run to run).

Results:

```
                        random  sorted  reverse  degenerate  big:64k  tiny:16
Old Sorting.quickSort     234     181      178         103    25,700      1.4
New Sorting.quickSort     170      27      115          74    18,600      0.8

Old Sorting.stableSort    321     234      236         282    32,600      2.1
New Sorting.stableSort    239      16      194         194    25,100      1.2

java.util.Arrays.sort     124       4        8         105    13,500      0.8
java.util.Arrays.sort|Box 126      15       13         112    13,200      0.9
```

The new versions are uniformly faster, but uniformly slower than Java sorting.  scala.util.Sorting has use cases that don't map easily in to Java unless everything is pre-boxed, but the overhead of pre-boxing is minimal compared to the sort.

A snapshot of some of my benchmarking code is below.

(Yes, lots of repeating myself--it's dangerous not to when trying to get
somewhat accurate benchmarks.)

```
import java.util.Arrays
import java.util.Comparator
import math.Ordering
import util.Sorting
import reflect.ClassTag

val th = ichi.bench.Thyme.warmed()

case class N(i: Int, j: Int) {}
val a = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt, i)) )
var ai = 0
val b = Array.fill(1024)( Array.tabulate(1024)(i => N(i, i)) )
var bi = 0
val c = Array.fill(1024)( Array.tabulate(1024)(i => N(1024-i, i)) )
var ci = 0
val d = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt(16), i)) )
var di = 0
val e = Array.fill(16)( Array.tabulate(65536)(i => N(util.Random.nextInt, i)) )
var ei = 0
val f = Array.fill(65535)( Array.tabulate(16)(i => N(util.Random.nextInt, i)) )
var fi = 0

val o = new Ordering[N]{ def compare(a: N, b: N) = if (a.i < b.i) -1 else if (a.i > b.i) 1 else 0 }
for (s <- Seq("one", "two", "three")) {
  println(s)
  th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Sorting.quickSort(x)(o); x(x.length/3) }
  th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Sorting.quickSort(x)(o); x(x.length/3) }
  th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Sorting.quickSort(x)(o); x(x.length/3) }
  th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Sorting.quickSort(x)(o); x(x.length/3) }
  th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Sorting.quickSort(x)(o); x(x.length/3) }
  th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Sorting.quickSort(x)(o); x(x.length/3) }
}

def ix(ns: Array[N]) = {
  val is = new Array[Int](ns.length)
  var i = 0
  while (i < ns.length) {
    is(i) = ns(i).i
    i += 1
  }
  is
}
val p = new Ordering[Int]{ def compare(a: Int, b: Int) = if (a > b) 1 else if (a < b) -1 else 0 }
for (s <- Seq("one", "two", "three")) {
  println(s)
  val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
  th.pbench{ val x = ix(a(ai)); ai = (ai+1)%a.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
  th.pbench{ val x = ix(b(bi)); bi = (bi+1)%b.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
  th.pbench{ val x = ix(c(ci)); ci = (ci+1)%c.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
  th.pbench{ val x = ix(d(di)); di = (di+1)%d.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
  th.pbench{ val x = ix(e(ei)); ei = (ei+1)%e.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
  th.pbench{ val x = ix(f(fi)); fi = (fi+1)%f.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
}

for (s <- Seq("one", "two", "three")) {
  println(s)
  th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Arrays.sort(x, o); x(x.length/3) }
  th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Arrays.sort(x, o); x(x.length/3) }
  th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Arrays.sort(x, o); x(x.length/3) }
  th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Arrays.sort(x, o); x(x.length/3) }
  th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Arrays.sort(x, o); x(x.length/3) }
  th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Arrays.sort(x, o); x(x.length/3) }
}

def bx(is: Array[Int]): Array[java.lang.Integer] = {
  val Is = new Array[java.lang.Integer](is.length)
  var i = 0
  while (i < is.length) {
    Is(i) = java.lang.Integer.valueOf(is(i))
    i += 1
  }
  Is
}
def xb(Is: Array[java.lang.Integer]): Array[Int] = {
  val is = new Array[Int](Is.length)
  var i = 0
  while (i < is.length) {
    is(i) = Is(i).intValue
    i += 1
  }
  is
}
val q = new Comparator[java.lang.Integer]{
  def compare(a: java.lang.Integer, b: java.lang.Integer) = o.compare(a.intValue, b.intValue)
}
for (s <- Seq("one", "two", "three")) {
  println(s)
  val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
  th.pbench{ val x = bx(ix(a(ai))); ai = (ai+1)%a.length; Arrays.sort(x, q); xb(x)(x.length/3) }
  th.pbench{ val x = bx(ix(b(bi))); bi = (bi+1)%b.length; Arrays.sort(x, q); xb(x)(x.length/3) }
  th.pbench{ val x = bx(ix(c(ci))); ci = (ci+1)%c.length; Arrays.sort(x, q); xb(x)(x.length/3) }
  th.pbench{ val x = bx(ix(d(di))); di = (di+1)%d.length; Arrays.sort(x, q); xb(x)(x.length/3) }
  th.pbench{ val x = bx(ix(e(ei))); ei = (ei+1)%e.length; Arrays.sort(x, q); xb(x)(x.length/3) }
  th.pbench{ val x = bx(ix(f(fi))); fi = (fi+1)%f.length; Arrays.sort(x, q); xb(x)(x.length/3) }
}
```

1 files changed, 69 insertions, 0 deletions

diff --git a/test/junit/scala/util/SortingTest.scala b/test/junit/scala/util/SortingTest.scala
new file mode 100644
index 0000000000..15a00c8903
--- /dev/null
+++ b/test/junit/scala/util/SortingTest.scala
@@ -0,0 +1,69 @@
+package scala.util
+
+import org.junit.Test
+import org.junit.Assert._
+import scala.math.{ Ordered, Ordering }
+import scala.reflect.ClassTag
+
+class SortingTest {
+  case class N(i: Int, j: Int) extends Ordered[N] { def compare(n: N) = if (i < n.i) -1 else if (i > n.i) 1 else 0 }
+
+  def mkA(n: Int, max: Int) = Array.tabulate(n)(i => N(util.Random.nextInt(max), i))
+  
+  def isStable(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true }
+  
+  def isAntistable(a: Array[N]): Boolean =
+    { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true }
+  
+  def isSorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i) return false; i += 1 }; true }
+  
+  def isAntisorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i) return false; i += 1 }; true }
+  
+  val sizes = Seq.range(0, 65) ++ Seq(256, 1024, 9121, 65539)
+  val variety = Seq(1, 2, 10, 100, 1000, Int.MaxValue)
+  val workLimit = 1e6
+  val rng = new util.Random(198571)
+  
+  val backwardsN = Ordering by ((n: N) => -n.i)
+  
+  def runOneTest(size: Int, variety: Int): Unit = {
+    val xs = Array.tabulate(size)(i => N(rng.nextInt(variety), i))
+    val ys = Array.range(0, xs.length)
+    val zs = { val temp = xs.clone; java.util.Arrays.sort(temp, new java.util.Comparator[N] { def compare(a: N, b: N) = a.compare(b) }); temp }
+    val qxs = { val temp = xs.clone; Sorting.quickSort(temp); temp }
+    val pxs = { val temp = xs.clone; Sorting.quickSort(temp)(backwardsN); temp }
+    val sxs = { val temp = xs.clone; Sorting.stableSort(temp); temp }
+    val rxs = { val temp = xs.clone; Sorting.stableSort(temp)(implicitly[ClassTag[N]], backwardsN); temp }
+    val sys = Sorting.stableSort(ys.clone: Seq[Int], (i: Int) => xs(i))
+    
+    assertTrue("Quicksort should be in order", isSorted(qxs))
+    assertTrue("Quicksort should be in reverse order", isAntisorted(pxs))
+    assertTrue("Stable sort should be sorted and stable", isStable(sxs))
+    assertTrue("Stable sort should be reverse sorted but stable", isAntistable(rxs))
+    assertTrue("Stable sorting by proxy should produce sorted stable list", isStable(sys.map(i => xs(i))))
+    assertTrue("Quicksort should produce canonical ordering", (qxs zip zs).forall{ case (a,b) => a.i == b.i })
+    assertTrue("Reverse quicksort should produce canonical ordering", (pxs.reverse zip zs).forall{ case (a,b) => a.i == b.i })
+    assertTrue("Stable sort should produce exact ordering", (sxs zip zs).forall{ case (a,b) => a == b })
+    assertTrue("Reverse stable sort should produce canonical ordering", (rxs.reverse zip zs).forall{ case (a,b) => a.i == b.i })
+    assertTrue("Proxy sort and direct sort should produce exactly the same thing", (sxs zip sys.map(i => xs(i))).forall{ case (a,b) => a == b })
+  }
+  
+  @Test def testSortConsistency: Unit = {
+    for {
+      size <- sizes
+      v <- variety
+      i <- 0 until math.min(100, math.max(math.min(math.floor(math.pow(v, size)/2), math.ceil(workLimit / (math.log(math.max(2,size))/math.log(2) * size))), 1).toInt)
+    } runOneTest(size, v)
+    
+    for (size <- sizes) {
+      val b = Array.fill(size)(rng.nextBoolean)
+      val bfwd = Sorting.stableSort(b.clone: Seq[Boolean])
+      val bbkw = Sorting.stableSort(b.clone: Seq[Boolean], (x: Boolean, y: Boolean) => x && !y)
+      assertTrue("All falses should be first", bfwd.dropWhile(_ == false).forall(_ == true))
+      assertTrue("All falses should be last when sorted backwards", bbkw.dropWhile(_ == true).forall(_ == false))
+      assertTrue("Sorting booleans should preserve the number of trues", b.count(_ == true) == bfwd.count(_ == true))
+      assertTrue("Backwards sorting booleans should preserve the number of trues", b.count(_ == true) == bbkw.count(_ == true))
+      assertTrue("Sorting should not change the sizes of arrays", b.length == bfwd.length && b.length == bbkw.length)
+    }
+  }
+}