Merge branch '2.11.x' into merge/2.11.x-to-2.12.x-20150624

16 files changed, 295 insertions, 542 deletions

diff --git a/src/library/scala/Function0.scala b/src/library/scala/Function0.scala
index e13aaad7bc..15d0f14938 100644
--- a/src/library/scala/Function0.scala
+++ b/src/library/scala/Function0.scala
@@ -6,7 +6,7 @@
 **                          |/                                          **
 \*                                                                      */
 // GENERATED CODE: DO NOT EDIT.
-// genprod generated these sources at: Sun Sep 15 20:42:00 CEST 2013
+// genprod generated these sources at: Mon Jun 08 18:05:40 CEST 2015
 
 package scala
 
@@ -26,12 +26,6 @@ package scala
  *    assert(javaVersion() == anonfun0())
  * }
  *  }}}
- *
- *  Note that `Function1` does not define a total function, as might
- *  be suggested by the existence of [[scala.PartialFunction]]. The only
- *  distinction between `Function1` and `PartialFunction` is that the
- *  latter can specify inputs which it will not handle.
-
  */
 trait Function0[@specialized(Specializable.Primitives) +R] extends AnyRef { self =>
   /** Apply the body of this function to the arguments.
diff --git a/src/library/scala/Function1.scala b/src/library/scala/Function1.scala
index 620dcc19aa..572901c6f3 100644
--- a/src/library/scala/Function1.scala
+++ b/src/library/scala/Function1.scala
@@ -25,11 +25,8 @@ package scala
  * }
  *  }}}
  *
- *  Note that `Function1` does not define a total function, as might
- *  be suggested by the existence of [[scala.PartialFunction]]. The only
- *  distinction between `Function1` and `PartialFunction` is that the
- *  latter can specify inputs which it will not handle.
-
+ *  Note that the difference between `Function1` and [[scala.PartialFunction]]
+ *  is that the latter can specify inputs which it will not handle.
  */
 @annotation.implicitNotFound(msg = "No implicit view available from ${T1} => ${R}.")
 trait Function1[@specialized(scala.Int, scala.Long, scala.Float, scala.Double) -T1, @specialized(scala.Unit, scala.Boolean, scala.Int, scala.Float, scala.Long, scala.Double) +R] extends AnyRef { self =>
diff --git a/src/library/scala/Function2.scala b/src/library/scala/Function2.scala
index 5690adb56a..e2c094ea40 100644
--- a/src/library/scala/Function2.scala
+++ b/src/library/scala/Function2.scala
@@ -25,12 +25,6 @@ package scala
  *    assert(max(0, 1) == anonfun2(0, 1))
  * }
  *  }}}
- *
- *  Note that `Function1` does not define a total function, as might
- *  be suggested by the existence of [[scala.PartialFunction]]. The only
- *  distinction between `Function1` and `PartialFunction` is that the
- *  latter can specify inputs which it will not handle.
-
  */
 trait Function2[@specialized(scala.Int, scala.Long, scala.Double) -T1, @specialized(scala.Int, scala.Long, scala.Double) -T2, @specialized(scala.Unit, scala.Boolean, scala.Int, scala.Float, scala.Long, scala.Double) +R] extends AnyRef { self =>
   /** Apply the body of this function to the arguments.
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala
index 5c4b15ad0f..e2c271145d 100644
--- a/src/library/scala/collection/Iterator.scala
+++ b/src/library/scala/collection/Iterator.scala
@@ -619,29 +619,21 @@ trait Iterator[+A] extends TraversableOnce[A] {
   def span(p: A => Boolean): (Iterator[A], Iterator[A]) = {
     val self = buffered
 
-    /*
-     * Giving a name to following iterator (as opposed to trailing) because
-     * anonymous class is represented as a structural type that trailing
-     * iterator is referring (the finish() method) and thus triggering
-     * handling of structural calls. It's not what's intended here.
-     */
+    // Must be a named class to avoid structural call to finish from trailing iterator
     class Leading extends AbstractIterator[A] {
-      val lookahead = new mutable.Queue[A]
-      def advance() = {
-        self.hasNext && p(self.head) && {
-          lookahead += self.next
-          true
-        }
+      private val drained  = new mutable.Queue[A]
+      private var finished = false
+      def finish(): Unit = {
+        require(!finished)
+        finished = true
+        while (selfish) drained += self.next
       }
-      def finish() = {
-        while (advance()) ()
-      }
-      def hasNext = lookahead.nonEmpty || advance()
+      private def selfish = self.hasNext && p(self.head)
+      def hasNext = if (finished) drained.nonEmpty else selfish
       def next() = {
-        if (lookahead.isEmpty)
-          advance()
-
-        lookahead.dequeue()
+        if (finished) drained.dequeue()
+        else if (selfish) self.next()
+        else empty.next()
       }
     }
     val leading = new Leading
diff --git a/src/library/scala/collection/generic/Sorted.scala b/src/library/scala/collection/generic/Sorted.scala
index a0b0e1318b..b2e63daaba 100644
--- a/src/library/scala/collection/generic/Sorted.scala
+++ b/src/library/scala/collection/generic/Sorted.scala
@@ -36,7 +36,7 @@ trait Sorted[K, +This <: Sorted[K, This]] {
   /** Creates a ranged projection of this collection. Any mutations in the
    *  ranged projection will update this collection and vice versa.
    *
-   *  Note: keys are not garuanteed to be consistent between this collection
+   *  Note: keys are not guaranteed to be consistent between this collection
    *  and the projection. This is the case for buffers where indexing is
    *  relative to the projection.
    *
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index 48a6ca5699..7b1997252d 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -462,6 +462,7 @@ object List extends SeqFactory[List] {
   private class SerializationProxy[A](@transient private var orig: List[A]) extends Serializable {
 
     private def writeObject(out: ObjectOutputStream) {
+      out.defaultWriteObject()
       var xs: List[A] = orig
       while (!xs.isEmpty) {
         out.writeObject(xs.head)
@@ -473,6 +474,7 @@ object List extends SeqFactory[List] {
     // Java serialization calls this before readResolve during de-serialization.
     // Read the whole list and store it in `orig`.
     private def readObject(in: ObjectInputStream) {
+      in.defaultReadObject()
       val builder = List.newBuilder[A]
       while (true) in.readObject match {
         case ListSerializeEnd =>
diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala
index f1ac161e9a..28e56a6d87 100644
--- a/src/library/scala/collection/immutable/NumericRange.scala
+++ b/src/library/scala/collection/immutable/NumericRange.scala
@@ -12,6 +12,9 @@ package immutable
 
 import mutable.{ Builder, ListBuffer }
 
+// TODO: Now the specialization exists there is no clear reason to have
+// separate classes for Range/NumericRange.  Investigate and consolidate.
+
 /** `NumericRange` is a more generic version of the
  *  `Range` class which works with arbitrary types.
  *  It must be supplied with an `Integral` implementation of the
@@ -28,9 +31,6 @@ import mutable.{ Builder, ListBuffer }
  *     assert(r1 sameElements r2.map(_ - veryBig))
  *  }}}
  *
- *  TODO: Now the specialization exists there is no clear reason to have
- *  separate classes for Range/NumericRange.  Investigate and consolidate.
- *
  *  @author  Paul Phillips
  *  @version 2.8
  *  @define Coll `NumericRange`
@@ -266,7 +266,7 @@ object NumericRange {
       // Numbers may be big.
       val one = num.one
       val limit = num.fromInt(Int.MaxValue)
-      def check(t: T): T = 
+      def check(t: T): T =
         if (num.gt(t, limit)) throw new IllegalArgumentException("More than Int.MaxValue elements.")
         else t
       // If the range crosses zero, it might overflow when subtracted
diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala
index 98266716cc..53af3ce158 100644
--- a/src/library/scala/collection/immutable/Queue.scala
+++ b/src/library/scala/collection/immutable/Queue.scala
@@ -56,11 +56,12 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A])
    *  @throws java.util.NoSuchElementException if the queue is too short.
    */
   override def apply(n: Int): A = {
-    val len = out.length
-    if (n < len) out.apply(n)
+    val olen = out.length
+    if (n < olen) out.apply(n)
     else {
-      val m = n - len
-      if (m < in.length) in.reverse.apply(m)
+      val m = n - olen
+      val ilen = in.length
+      if (m < ilen) in.apply(ilen - m - 1)
       else throw new NoSuchElementException("index out of range")
     }
   }
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index ada3533a60..6c5b10e73b 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -153,7 +153,7 @@ import scala.language.implicitConversions
  *
  *  - The fact that `tail` works at all is of interest.  In the definition of
  *  `fibs` we have an initial `(0, 1, Stream(...))` so `tail` is deterministic.
- *  If we deinfed `fibs` such that only `0` were concretely known then the act
+ *  If we defined `fibs` such that only `0` were concretely known then the act
  *  of determining `tail` would require the evaluation of `tail` which would
  *  cause an infinite recursion and stack overflow.  If we define a definition
  *  where the tail is not initially computable then we're going to have an
@@ -1134,7 +1134,13 @@ object Stream extends SeqFactory[Stream] {
    *  to streams.
    */
   class ConsWrapper[A](tl: => Stream[A]) {
+    /** Construct a stream consisting of a given first element followed by elements
+     *  from a lazily evaluated Stream.
+     */
     def #::(hd: A): Stream[A] = cons(hd, tl)
+    /** Construct a stream consisting of the concatenation of the given stream and
+     *  a lazily evaluated Stream.
+     */
     def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
   }
 
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 47a623a616..46d5d0c69c 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -132,19 +132,25 @@ override def companion: GenericCompanion[Vector] = Vector
       throw new IndexOutOfBoundsException(index.toString)
   }
 
-
+  // If we have a default builder, there are faster ways to perform some operations
+  @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean =
+    (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF)
+    
   // SeqLike api
 
   override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That =
-    if (bf eq IndexedSeq.ReusableCBF) updateAt(index, elem).asInstanceOf[That] // just ignore bf
+    if (isDefaultCBF[A, B, That](bf))
+      updateAt(index, elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly
     else super.updated(index, elem)(bf)
 
   override def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That =
-    if (bf eq IndexedSeq.ReusableCBF) appendFront(elem).asInstanceOf[That] // just ignore bf
+    if (isDefaultCBF[A, B, That](bf))
+      appendFront(elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly
     else super.+:(elem)(bf)
 
   override def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That =
-    if (bf eq IndexedSeq.ReusableCBF) appendBack(elem).asInstanceOf[That] // just ignore bf
+    if (isDefaultCBF(bf))
+      appendBack(elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly
     else super.:+(elem)(bf)
 
   override def take(n: Int): Vector[A] = {
@@ -211,7 +217,8 @@ override def companion: GenericCompanion[Vector] = Vector
 
   // concat (suboptimal but avoids worst performance gotchas)
   override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = {
-    if (bf eq IndexedSeq.ReusableCBF) {
+    if (isDefaultCBF(bf)) {
+      // We are sure we will create a Vector, so let's do it efficiently
       import Vector.{Log2ConcatFaster, TinyAppendFaster}
       if (that.isEmpty) this.asInstanceOf[That]
       else {
diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala
index 1906c47f61..2bc6738e53 100644
--- a/src/library/scala/collection/mutable/ListBuffer.scala
+++ b/src/library/scala/collection/mutable/ListBuffer.scala
@@ -15,7 +15,7 @@ import immutable.{List, Nil, ::}
 import java.io.{ObjectOutputStream, ObjectInputStream}
 import scala.annotation.migration
 
-/** A `Buffer` implementation back up by a list. It provides constant time
+/** A `Buffer` implementation backed by a list. It provides constant time
  *  prepend and append. Most other operations are linear.
  *
  *  @author  Matthias Zenger
diff --git a/src/library/scala/math/BigDecimal.scala b/src/library/scala/math/BigDecimal.scala
index d6e2963ad8..6bb35606a6 100644
--- a/src/library/scala/math/BigDecimal.scala
+++ b/src/library/scala/math/BigDecimal.scala
@@ -49,7 +49,7 @@ object BigDecimal {
   
   /** Constructs a `BigDecimal` using the decimal text representation of `Double` value `d`, rounding if necessary. */
   def decimal(d: Double, mc: MathContext): BigDecimal =
-    new BigDecimal(new BigDec(java.lang.Double.toString(d), mc))
+    new BigDecimal(new BigDec(java.lang.Double.toString(d), mc), mc)
 
   /** Constructs a `BigDecimal` using the decimal text representation of `Double` value `d`. */
   def decimal(d: Double): BigDecimal = decimal(d, defaultMathContext)
@@ -59,7 +59,7 @@ object BigDecimal {
    *  `0.1 != 0.1f`.
    */
   def decimal(f: Float, mc: MathContext): BigDecimal =
-    new BigDecimal(new BigDec(java.lang.Float.toString(f), mc))
+    new BigDecimal(new BigDec(java.lang.Float.toString(f), mc), mc)
 
   /** Constructs a `BigDecimal` using the decimal text representation of `Float` value `f`.
    *  Note that `BigDecimal.decimal(0.1f) != 0.1f` since equality agrees with the `Double` representation, and
diff --git a/src/library/scala/math/Numeric.scala b/src/library/scala/math/Numeric.scala
index eafbf96993..9245798c17 100644
--- a/src/library/scala/math/Numeric.scala
+++ b/src/library/scala/math/Numeric.scala
@@ -134,7 +134,7 @@ object Numeric {
     def div(x: Float, y: Float): Float = x / y
   }
   trait FloatAsIfIntegral extends FloatIsConflicted with Integral[Float] {
-    def quot(x: Float, y: Float): Float = (BigDecimal(x) / BigDecimal(y)).floatValue
+    def quot(x: Float, y: Float): Float = (BigDecimal(x) quot BigDecimal(y)).floatValue
     def rem(x: Float, y: Float): Float = (BigDecimal(x) remainder BigDecimal(y)).floatValue
   }
   implicit object FloatIsFractional extends FloatIsFractional with Ordering.FloatOrdering
@@ -158,7 +158,7 @@ object Numeric {
     def div(x: Double, y: Double): Double = x / y
   }
   trait DoubleAsIfIntegral extends DoubleIsConflicted with Integral[Double] {
-    def quot(x: Double, y: Double): Double = (BigDecimal(x) / BigDecimal(y)).doubleValue
+    def quot(x: Double, y: Double): Double = (BigDecimal(x) quot BigDecimal(y)).doubleValue
     def rem(x: Double, y: Double): Double = (BigDecimal(x) remainder BigDecimal(y)).doubleValue
   }
 
@@ -178,7 +178,7 @@ object Numeric {
     def div(x: BigDecimal, y: BigDecimal): BigDecimal = x / y
   }
   trait BigDecimalAsIfIntegral extends BigDecimalIsConflicted with Integral[BigDecimal] {
-    def quot(x: BigDecimal, y: BigDecimal): BigDecimal = x / y
+    def quot(x: BigDecimal, y: BigDecimal): BigDecimal = x quot y
     def rem(x: BigDecimal, y: BigDecimal): BigDecimal = x remainder y
   }
 
diff --git a/src/library/scala/sys/BooleanProp.scala b/src/library/scala/sys/BooleanProp.scala
index 74b0a9077b..e5e4668edb 100644
--- a/src/library/scala/sys/BooleanProp.scala
+++ b/src/library/scala/sys/BooleanProp.scala
@@ -63,12 +63,13 @@ object BooleanProp {
   def valueIsTrue[T](key: String): BooleanProp = new BooleanPropImpl(key, _.toLowerCase == "true")
 
   /** As an alternative, this method creates a BooleanProp which is true
-   *  if the key exists in the map.  This way -Dfoo.bar is enough to be
-   *  considered true.
+   *  if the key exists in the map and is not assigned a value other than "true",
+   *  compared case-insensitively, or the empty string.  This way -Dmy.property
+   *  results in a true-valued property, but -Dmy.property=false does not.
    *
    *  @return   A BooleanProp with a liberal truth policy
    */
-  def keyExists[T](key: String): BooleanProp = new BooleanPropImpl(key, _ => true)
+  def keyExists[T](key: String): BooleanProp = new BooleanPropImpl(key, s => s == "" || s.equalsIgnoreCase("true"))
 
   /** A constant true or false property which ignores all method calls.
    */
diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala
index 2e021ad9d9..ee2bdbc4a7 100644
--- a/src/library/scala/util/Sorting.scala
+++ b/src/library/scala/util/Sorting.scala
@@ -1,6 +1,6 @@
 /*                     __                                               *\
 **     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2006-2009, Ross Judson           **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2015, LAMP/EPFL             **
 **  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
 ** /____/\___/_/ |_/____/_/ | |                                         **
 **                          |/                                          **
@@ -9,518 +9,276 @@
 package scala
 package util
 
-import scala.reflect.{ ClassTag, classTag }
-import scala.math.{ Ordering, max, min }
+import scala.reflect.ClassTag
+import scala.math.Ordering
 
-/** The Sorting object provides functions that can sort various kinds of
-  * objects. You can provide a comparison function, or you can request a sort
-  * of items that are viewable as [[scala.math.Ordered]]. Some sorts that
-  * operate directly on a subset of value types are also provided. These
-  * implementations are derived from those in the Sun JDK.
+/** The `Sorting` object provides convenience wrappers for `java.util.Arrays.sort`.
+  * Methods that defer to `java.util.Arrays.sort` say that they do or under what
+  * conditions that they do.
   *
-  * Note that stability doesn't matter for value types, so use the `quickSort`
-  * variants for those. `stableSort` is intended to be used with
-  * objects when the prior ordering should be preserved, where possible.
+  * `Sorting` also implements a general-purpose quicksort and stable (merge) sort
+  * for those cases where `java.util.Arrays.sort` could only be used at the cost
+  * of a large memory penalty.  If performance rather than memory usage is the
+  * primary concern, one may wish to find alternate strategies to use
+  * `java.util.Arrays.sort` directly e.g. by boxing primitives to use
+  * a custom ordering on them.
+  *
+  * `Sorting` provides methods where you can provide a comparison function, or
+  * can request a sort of items that are [[scala.math.Ordered]] or that
+  * otherwise have an implicit or explicit [[scala.math.Ordering]].
+  *
+  * Note also that high-performance non-default sorts for numeric types
+  * are not provided.  If this is required, it is advisable to investigate
+  * other libraries that cover this use case.
   *
   * @author  Ross Judson
-  * @version 1.0
+  * @author  Adriaan Moors
+  * @author  Rex Kerr
+  * @version 1.1
   */
 object Sorting {
-  /** Quickly sort an array of Doubles. */
-  def quickSort(a: Array[Double]) { sort1(a, 0, a.length) }
-
-  /** Quickly sort an array of items with an implicit Ordering. */
-  def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) }
-
-  /** Quickly sort an array of Ints. */
-  def quickSort(a: Array[Int]) { sort1(a, 0, a.length) }
-
-  /** Quickly sort an array of Floats. */
-  def quickSort(a: Array[Float]) { sort1(a, 0, a.length) }
-
-  /** Sort an array of K where K is Ordered, preserving the existing order
-    * where the values are equal. */
-  def stableSort[K: ClassTag: Ordering](a: Array[K]) {
-    stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _)
-  }
+  /** Sort an array of Doubles using `java.util.Arrays.sort`. */
+  def quickSort(a: Array[Double]): Unit = java.util.Arrays.sort(a)
 
-  /** Sorts an array of `K` given an ordering function `f`.
-   *  `f` should return `true` iff its first parameter is strictly less than its second parameter.
-   */
-  def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean) {
-    stableSort(a, 0, a.length-1, new Array[K](a.length), f)
-  }
+  /** Sort an array of Ints using `java.util.Arrays.sort`. */
+  def quickSort(a: Array[Int]): Unit    = java.util.Arrays.sort(a)
 
-  /** Sorts an arbitrary sequence into an array, given a comparison function
-   *  that should return `true` iff parameter one is strictly less than parameter two.
-   *
-   *  @param  a the sequence to be sorted.
-   *  @param  f the comparison function.
-   *  @return the sorted sequence of items.
-   */
-  def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = {
-    val ret = a.toArray
-    stableSort(ret, f)
-    ret
-  }
+  /** Sort an array of Floats using `java.util.Arrays.sort`. */
+  def quickSort(a: Array[Float]): Unit  = java.util.Arrays.sort(a)
+  
+  private final val qsortThreshold = 16
 
-  /** Sorts an arbitrary sequence of items that are viewable as ordered. */
-  def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] =
-    stableSort(a, Ordering[K].lt _)
-
-  /** Stably sorts a sequence of items given an extraction function that will
-   *  return an ordered key from an item.
-   *
-   *  @param  a the sequence to be sorted.
-   *  @param  f the comparison function.
-   *  @return the sorted sequence of items.
-   */
-  def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] =
-    stableSort(a)(implicitly[ClassTag[K]], Ordering[M] on f)
-
-  private def sort1[K: Ordering](x: Array[K], off: Int, len: Int) {
-    val ord = Ordering[K]
-    import ord._
-
-    def swap(a: Int, b: Int) {
-      val t = x(a)
-      x(a) = x(b)
-      x(b) = t
-    }
-    def vecswap(_a: Int, _b: Int, n: Int) {
-      var a = _a
-      var b = _b
-      var i = 0
-      while (i < n) {
-        swap(a, b)
-        i += 1
-        a += 1
-        b += 1
-      }
-    }
-    def med3(a: Int, b: Int, c: Int) = {
-      if (x(a) < x(b)) {
-        if (x(b) < x(c)) b else if (x(a) < x(c)) c else a
-      } else {
-        if (x(b) > x(c)) b else if (x(a) > x(c)) c else a
-      }
-    }
-    def sort2(off: Int, len: Int) {
-      // Insertion sort on smallest arrays
-      if (len < 7) {
-        var i = off
-        while (i < len + off) {
-          var j = i
-          while (j > off && x(j-1) > x(j)) {
-            swap(j, j-1)
-            j -= 1
+  /** Sort array `a` with quicksort, using the Ordering on its elements.
+    * This algorithm sorts in place, so no additional memory is used aside from
+    * what might be required to box individual elements during comparison.
+    */
+  def quickSort[K: Ordering](a: Array[K]): Unit = {
+    // Must have iN >= i0 or math will fail.  Also, i0 >= 0.
+    def inner(a: Array[K], i0: Int, iN: Int, ord: Ordering[K]): Unit = {
+      if (iN - i0 < qsortThreshold) insertionSort(a, i0, iN, ord)
+      else {
+        var iK = (i0 + iN) >>> 1    // Unsigned div by 2
+        // Find index of median of first, central, and last elements
+        var pL = 
+          if (ord.compare(a(i0), a(iN - 1)) <= 0)
+            if (ord.compare(a(i0), a(iK)) < 0)
+              if (ord.compare(a(iN - 1), a(iK)) < 0) iN - 1 else iK
+            else i0
+          else
+            if (ord.compare(a(i0), a(iK)) < 0) i0
+            else
+              if (ord.compare(a(iN - 1), a(iK)) <= 0) iN - 1
+              else iK
+        val pivot = a(pL)
+        // pL is the start of the pivot block; move it into the middle if needed
+        if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK }
+        // Elements equal to the pivot will be in range pL until pR
+        var pR = pL + 1
+        // Items known to be less than pivot are below iA (range i0 until iA)
+        var iA = i0
+        // Items known to be greater than pivot are at or above iB (range iB until iN)
+        var iB = iN
+        // Scan through everything in the buffer before the pivot(s)
+        while (pL - iA > 0) {
+          val current = a(iA)
+          ord.compare(current, pivot) match {
+            case 0 =>
+              // Swap current out with pivot block
+              a(iA) = a(pL - 1)
+              a(pL - 1) = current
+              pL -= 1
+            case x if x < 0 =>
+              // Already in place.  Just update indicies.
+              iA += 1
+            case _ if iB > pR =>
+              // Wrong side.  There's room on the other side, so swap
+              a(iA) = a(iB - 1)
+              a(iB - 1) = current
+              iB -= 1
+            case _ =>
+              // Wrong side and there is no room.  Swap by rotating pivot block.
+              a(iA) = a(pL - 1)
+              a(pL - 1) = a(pR - 1)
+              a(pR - 1) = current
+              pL -= 1
+              pR -= 1
+              iB -= 1
           }
-          i += 1
         }
-      } else {
-        // Choose a partition element, v
-        var m = off + (len >> 1)        // Small arrays, middle element
-        if (len > 7) {
-          var l = off
-          var n = off + len - 1
-          if (len > 40) {        // Big arrays, pseudomedian of 9
-            val s = len / 8
-            l = med3(l, l+s, l+2*s)
-            m = med3(m-s, m, m+s)
-            n = med3(n-2*s, n-s, n)
+        // Get anything remaining in buffer after the pivot(s)
+        while (iB - pR > 0) {
+          val current = a(iB - 1)
+          ord.compare(current, pivot) match {
+            case 0 =>
+              // Swap current out with pivot block
+              a(iB - 1) = a(pR)
+              a(pR) = current
+              pR += 1
+            case x if x > 0 =>
+              // Already in place.  Just update indices.
+              iB -= 1
+            case _ =>
+              // Wrong side and we already know there is no room.  Swap by rotating pivot block.
+              a(iB - 1) = a(pR)
+              a(pR) = a(pL)
+              a(pL) = current
+              iA += 1
+              pL += 1
+              pR += 1
           }
-          m = med3(l, m, n) // Mid-size, med of 3
         }
-        val v = x(m)
-
-        // Establish Invariant: v* (<v)* (>v)* v*
-        var a = off
-        var b = a
-        var c = off + len - 1
-        var d = c
-        var done = false
-        while (!done) {
-          while (b <= c && x(b) <= v) {
-            if (x(b) equiv v) {
-              swap(a, b)
-              a += 1
-            }
-            b += 1
-          }
-          while (c >= b && x(c) >= v) {
-            if (x(c) equiv v) {
-              swap(c, d)
-              d -= 1
-            }
-            c -= 1
-          }
-          if (b > c) {
-            done = true
-          } else {
-            swap(b, c)
-            c -= 1
-            b += 1
-          }
+        // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen
+        if (iA - i0 < iN - iB) {
+          inner(a, i0, iA, ord)  // True recursion
+          inner(a, iB, iN, ord)  // Should be tail recursion
+        }
+        else {
+          inner(a, iB, iN, ord)  // True recursion
+          inner(a, i0, iA, ord)  // Should be tail recursion
         }
-
-        // Swap partition elements back to middle
-        val n = off + len
-        var s = math.min(a-off, b-a)
-        vecswap(off, b-s, s)
-        s = math.min(d-c, n-d-1)
-        vecswap(b,   n-s, s)
-
-        // Recursively sort non-partition-elements
-        s = b - a
-        if (s > 1)
-          sort2(off, s)
-        s = d - c
-        if (s > 1)
-          sort2(n-s, s)
       }
     }
-    sort2(off, len)
+    inner(a, 0, a.length, implicitly[Ordering[K]])
   }
-
-  private def sort1(x: Array[Int], off: Int, len: Int) {
-    def swap(a: Int, b: Int) {
-      val t = x(a)
-      x(a) = x(b)
-      x(b) = t
+  
+  private final val mergeThreshold = 32
+  
+  // Ordering[T] might be slow especially for boxed primitives, so use binary search variant of insertion sort
+  // Caller must pass iN >= i0 or math will fail.  Also, i0 >= 0.
+  private def insertionSort[@specialized T](a: Array[T], i0: Int, iN: Int, ord: Ordering[T]): Unit = {
+    val n = iN - i0
+    if (n < 2) return
+    if (ord.compare(a(i0), a(i0+1)) > 0) {
+      val temp = a(i0)
+      a(i0) = a(i0+1)
+      a(i0+1) = temp
     }
-    def vecswap(_a: Int, _b: Int, n: Int) {
-      var a = _a
-      var b = _b
-      var i = 0
-      while (i < n) {
-        swap(a, b)
-        i += 1
-        a += 1
-        b += 1
-      }
-    }
-    def med3(a: Int, b: Int, c: Int) = {
-      if (x(a) < x(b)) {
-        if (x(b) < x(c)) b else if (x(a) < x(c)) c else a
-      } else {
-        if (x(b) > x(c)) b else if (x(a) > x(c)) c else a
-      }
-    }
-    def sort2(off: Int, len: Int) {
-      // Insertion sort on smallest arrays
-      if (len < 7) {
-        var i = off
-        while (i < len + off) {
-          var j = i
-          while (j>off && x(j-1) > x(j)) {
-            swap(j, j-1)
-            j -= 1
-          }
-          i += 1
+    var m = 2
+    while (m < n) {
+      // Speed up already-sorted case by checking last element first
+      val next = a(i0 + m)
+      if (ord.compare(next, a(i0+m-1)) < 0) {
+        var iA = i0
+        var iB = i0 + m - 1
+        while (iB - iA > 1) {
+          val ix = (iA + iB) >>> 1    // Use bit shift to get unsigned div by 2
+          if (ord.compare(next, a(ix)) < 0) iB = ix
+          else iA = ix
         }
-      } else {
-        // Choose a partition element, v
-        var m = off + (len >> 1)        // Small arrays, middle element
-        if (len > 7) {
-          var l = off
-          var n = off + len - 1
-          if (len > 40) {        // Big arrays, pseudomedian of 9
-            val s = len / 8
-            l = med3(l, l+s, l+2*s)
-            m = med3(m-s, m, m+s)
-            n = med3(n-2*s, n-s, n)
-          }
-          m = med3(l, m, n) // Mid-size, med of 3
-        }
-        val v = x(m)
-
-        // Establish Invariant: v* (<v)* (>v)* v*
-        var a = off
-        var b = a
-        var c = off + len - 1
-        var d = c
-        var done = false
-        while (!done) {
-          while (b <= c && x(b) <= v) {
-            if (x(b) == v) {
-              swap(a, b)
-              a += 1
-            }
-            b += 1
-          }
-          while (c >= b && x(c) >= v) {
-            if (x(c) == v) {
-              swap(c, d)
-              d -= 1
-            }
-            c -= 1
-          }
-          if (b > c) {
-            done = true
-          } else {
-            swap(b, c)
-            c -= 1
-            b += 1
-          }
+        val ix = iA + (if (ord.compare(next, a(iA)) < 0) 0 else 1)
+        var i = i0 + m
+        while (i > ix) {
+          a(i) = a(i-1)
+          i -= 1
         }
-
-        // Swap partition elements back to middle
-        val n = off + len
-        var s = math.min(a-off, b-a)
-        vecswap(off, b-s, s)
-        s = math.min(d-c, n-d-1)
-        vecswap(b,   n-s, s)
-
-        // Recursively sort non-partition-elements
-        s = b - a
-        if (s > 1)
-          sort2(off, s)
-        s = d - c
-        if (s > 1)
-          sort2(n-s, s)
+        a(ix) = next
       }
+      m += 1
     }
-    sort2(off, len)
   }
-
-  private def sort1(x: Array[Double], off: Int, len: Int) {
-    def swap(a: Int, b: Int) {
-      val t = x(a)
-      x(a) = x(b)
-      x(b) = t
+  
+  // Caller is required to pass iN >= i0, else math will fail.  Also, i0 >= 0.
+  private def mergeSort[@specialized T: ClassTag](a: Array[T], i0: Int, iN: Int, ord: Ordering[T], scratch: Array[T] = null): Unit = {
+    if (iN - i0 < mergeThreshold) insertionSort(a, i0, iN, ord)
+    else {
+      val iK = (i0 + iN) >>> 1   // Bit shift equivalent to unsigned math, no overflow
+      val sc = if (scratch eq null) new Array[T](iK - i0) else scratch
+      mergeSort(a, i0, iK, ord, sc)
+      mergeSort(a, iK, iN, ord, sc)
+      mergeSorted(a, i0, iK, iN, ord, sc)
     }
-    def vecswap(_a: Int, _b: Int, n: Int) {
-      var a = _a
-      var b = _b
-      var i = 0
-      while (i < n) {
-        swap(a, b)
+  }
+  
+  // Must have 0 <= i0 < iK < iN
+  private def mergeSorted[@specialized T](a: Array[T], i0: Int, iK: Int, iN: Int, ord: Ordering[T], scratch: Array[T]): Unit = {
+    // Check to make sure we're not already in order
+    if (ord.compare(a(iK-1), a(iK)) > 0) {
+      var i = i0
+      val jN = iK - i0
+      var j = 0
+      while (i < iK) {
+        scratch (j) = a(i)
         i += 1
-        a += 1
-        b += 1
-      }
-    }
-    def med3(a: Int, b: Int, c: Int) = {
-      val ab = x(a) compare x(b)
-      val bc = x(b) compare x(c)
-      val ac = x(a) compare x(c)
-      if (ab < 0) {
-        if (bc < 0) b else if (ac < 0) c else a
-      } else {
-        if (bc > 0) b else if (ac > 0) c else a
+        j += 1
       }
-    }
-    def sort2(off: Int, len: Int) {
-      // Insertion sort on smallest arrays
-      if (len < 7) {
-        var i = off
-        while (i < len + off) {
-          var j = i
-          while (j > off && (x(j-1) compare x(j)) > 0) {
-            swap(j, j-1)
-            j -= 1
-          }
-          i += 1
-        }
-      } else {
-        // Choose a partition element, v
-        var m = off + (len >> 1)        // Small arrays, middle element
-        if (len > 7) {
-          var l = off
-          var n = off + len - 1
-          if (len > 40) {        // Big arrays, pseudomedian of 9
-            val s = len / 8
-            l = med3(l, l+s, l+2*s)
-            m = med3(m-s, m, m+s)
-            n = med3(n-2*s, n-s, n)
-          }
-          m = med3(l, m, n) // Mid-size, med of 3
-        }
-        val v = x(m)
-
-        // Establish Invariant: v* (<v)* (>v)* v*
-        var a = off
-        var b = a
-        var c = off + len - 1
-        var d = c
-        var done = false
-        while (!done) {
-          var bv = x(b) compare v
-          while (b <= c && bv <= 0) {
-            if (bv == 0) {
-              swap(a, b)
-              a += 1
-            }
-            b += 1
-            if (b <= c) bv = x(b) compare v
-          }
-          var cv = x(c) compare v
-          while (c >= b && cv >= 0) {
-            if (cv == 0) {
-              swap(c, d)
-              d -= 1
-            }
-            c -= 1
-            if (c >= b) cv = x(c) compare v
-          }
-          if (b > c) {
-            done = true
-          } else {
-            swap(b, c)
-            c -= 1
-            b += 1
-          }
-        }
-
-        // Swap partition elements back to middle
-        val n = off + len
-        var s = math.min(a-off, b-a)
-        vecswap(off, b-s, s)
-        s = math.min(d-c, n-d-1)
-        vecswap(b,   n-s, s)
-
-        // Recursively sort non-partition-elements
-        s = b - a
-        if (s > 1)
-          sort2(off, s)
-        s = d - c
-        if (s > 1)
-          sort2(n-s, s)
+      var k = i0
+      j = 0
+      while (i < iN && j < jN) {
+        if (ord.compare(a(i), scratch(j)) < 0) { a(k) = a(i); i += 1 }
+        else { a(k) = scratch(j); j += 1 }
+        k += 1
       }
+      while (j < jN) { a(k) = scratch(j); j += 1; k += 1 }
+      // Don't need to finish a(i) because it's already in place, k = i
     }
-    sort2(off, len)
   }
-
-  private def sort1(x: Array[Float], off: Int, len: Int) {
-    def swap(a: Int, b: Int) {
-      val t = x(a)
-      x(a) = x(b)
-      x(b) = t
+  
+  // Why would you even do this?
+  private def booleanSort(a: Array[Boolean]): Unit = {
+    var i = 0
+    var n = 0
+    while (i < a.length) {
+      if (!a(i)) n += 1
+      i += 1
     }
-    def vecswap(_a: Int, _b: Int, n: Int) {
-      var a = _a
-      var b = _b
-      var i = 0
-      while (i < n) {
-        swap(a, b)
-        i += 1
-        a += 1
-        b += 1
-      }
+    i = 0
+    while (i < n) {
+      a(i) = false
+      i += 1
     }
-    def med3(a: Int, b: Int, c: Int) = {
-      val ab = x(a) compare x(b)
-      val bc = x(b) compare x(c)
-      val ac = x(a) compare x(c)
-      if (ab < 0) {
-        if (bc < 0) b else if (ac < 0) c else a
-      } else {
-        if (bc > 0) b else if (ac > 0) c else a
-      }
+    while (i < a.length) {
+      a(i) = true
+      i += 1
     }
-    def sort2(off: Int, len: Int) {
-      // Insertion sort on smallest arrays
-      if (len < 7) {
-        var i = off
-        while (i < len + off) {
-          var j = i
-          while (j > off && (x(j-1) compare x(j)) > 0) {
-            swap(j, j-1)
-            j -= 1
-          }
-          i += 1
-        }
-      } else {
-        // Choose a partition element, v
-        var m = off + (len >> 1)        // Small arrays, middle element
-        if (len > 7) {
-          var l = off
-          var n = off + len - 1
-          if (len > 40) {        // Big arrays, pseudomedian of 9
-            val s = len / 8
-            l = med3(l, l+s, l+2*s)
-            m = med3(m-s, m, m+s)
-            n = med3(n-2*s, n-s, n)
-          }
-          m = med3(l, m, n) // Mid-size, med of 3
-        }
-        val v = x(m)
+  }
 
-        // Establish Invariant: v* (<v)* (>v)* v*
-        var a = off
-        var b = a
-        var c = off + len - 1
-        var d = c
-        var done = false
-        while (!done) {
-          var bv = x(b) compare v
-          while (b <= c && bv <= 0) {
-            if (bv == 0) {
-              swap(a, b)
-              a += 1
-            }
-            b += 1
-            if (b <= c) bv = x(b) compare v
-          }
-          var cv = x(c) compare v
-          while (c >= b && cv >= 0) {
-            if (cv == 0) {
-              swap(c, d)
-              d -= 1
-            }
-            c -= 1
-            if (c >= b) cv = x(c) compare v
-          }
-          if (b > c) {
-            done = true
-          } else {
-            swap(b, c)
-            c -= 1
-            b += 1
-          }
-        }
+  // TODO: add upper bound: T <: AnyRef, propagate to callers below (not binary compatible)
+  // Maybe also rename all these methods to `sort`.
+  @inline private def sort[T](a: Array[T], ord: Ordering[T]): Unit = a match {
+    case _: Array[AnyRef]  => 
+      // Note that runtime matches are covariant, so could actually be any Array[T] s.t. T is not primitive (even boxed value classes)
+      if (a.length > 1 && (ord eq null)) throw new NullPointerException("Ordering")
+      java.util.Arrays.sort(a, ord)
+    case a: Array[Int]     => if (ord eq Ordering.Int) java.util.Arrays.sort(a) else mergeSort[Int](a, 0, a.length, ord)
+    case a: Array[Double]  => mergeSort[Double](a, 0, a.length, ord)  // Because not all NaNs are identical, stability is meaningful!
+    case a: Array[Long]    => if (ord eq Ordering.Long) java.util.Arrays.sort(a) else mergeSort[Long](a, 0, a.length, ord)
+    case a: Array[Float]   => mergeSort[Float](a, 0, a.length, ord)   // Because not all NaNs are identical, stability is meaningful!
+    case a: Array[Char]    => if (ord eq Ordering.Char) java.util.Arrays.sort(a) else mergeSort[Char](a, 0, a.length, ord)
+    case a: Array[Byte]    => if (ord eq Ordering.Byte) java.util.Arrays.sort(a) else mergeSort[Byte](a, 0, a.length, ord)
+    case a: Array[Short]   => if (ord eq Ordering.Short) java.util.Arrays.sort(a) else mergeSort[Short](a, 0, a.length, ord)
+    case a: Array[Boolean] => if (ord eq Ordering.Boolean) booleanSort(a) else mergeSort[Boolean](a, 0, a.length, ord)
+    // Array[Unit] is matched as an Array[AnyRef] due to covariance in runtime matching.  Not worth catching it as a special case.
+    case null => throw new NullPointerException
+  }
 
-        // Swap partition elements back to middle
-        val n = off + len
-        var s = math.min(a-off, b-a)
-        vecswap(off, b-s, s)
-        s = math.min(d-c, n-d-1)
-        vecswap(b,   n-s, s)
+  // TODO: remove unnecessary ClassTag (not binary compatible)
+  /** Sort array `a` using the Ordering on its elements, preserving the original ordering where possible.  Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+  def stableSort[K: ClassTag: Ordering](a: Array[K]): Unit = sort(a, Ordering[K])
 
-        // Recursively sort non-partition-elements
-        s = b - a
-        if (s > 1)
-          sort2(off, s)
-        s = d - c
-        if (s > 1)
-          sort2(n-s, s)
-      }
-    }
-    sort2(off, len)
+  // TODO: Remove unnecessary ClassTag (not binary compatible)
+  // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering)
+  /** Sort array `a` using function `f` that computes the less-than relation for each element.  Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+  def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean): Unit = sort(a, Ordering fromLessThan f)
+
+  /** A sorted Array, using the Ordering for the elements in the sequence `a`.  Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+  def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = {
+    val ret = a.toArray
+    sort(ret, Ordering[K])
+    ret
   }
 
-  private def stableSort[K : ClassTag](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) {
-    if (lo < hi) {
-      val mid = (lo+hi) / 2
-      stableSort(a, lo, mid, scratch, f)
-      stableSort(a, mid+1, hi, scratch, f)
-      var k, t_lo = lo
-      var t_hi = mid + 1
-      while (k <= hi) {
-        if ((t_lo <= mid) && ((t_hi > hi) || (!f(a(t_hi), a(t_lo))))) {
-          scratch(k) = a(t_lo)
-          t_lo += 1
-        } else {
-          scratch(k) = a(t_hi)
-          t_hi += 1
-        }
-        k += 1
-      }
-      k = lo
-      while (k <= hi) {
-        a(k) = scratch(k)
-        k += 1
-      }
-    }
+  // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering)
+  /** A sorted Array, given a function `f` that computes the less-than relation for each item in the sequence `a`.  Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+  def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = {
+    val ret = a.toArray
+    sort(ret, Ordering fromLessThan f)
+    ret
+  }
+
+  /** A sorted Array, given an extraction function `f` that returns an ordered key for each item in the sequence `a`.  Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+  def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = {
+    val ret = a.toArray
+    sort(ret, Ordering[M] on f)
+    ret
   }
 }
diff --git a/src/library/scala/util/Try.scala b/src/library/scala/util/Try.scala
index 1a13ac2305..b1b9965614 100644
--- a/src/library/scala/util/Try.scala
+++ b/src/library/scala/util/Try.scala
@@ -24,11 +24,12 @@ import scala.language.implicitConversions
  *
  * Example:
  * {{{
+ *   import scala.io.StdIn
  *   import scala.util.{Try, Success, Failure}
  *
  *   def divide: Try[Int] = {
- *     val dividend = Try(Console.readLine("Enter an Int that you'd like to divide:\n").toInt)
- *     val divisor = Try(Console.readLine("Enter an Int that you'd like to divide by:\n").toInt)
+ *     val dividend = Try(StdIn.readLine("Enter an Int that you'd like to divide:\n").toInt)
+ *     val divisor = Try(StdIn.readLine("Enter an Int that you'd like to divide by:\n").toInt)
  *     val problem = dividend.flatMap(x => divisor.map(y => x/y))
  *     problem match {
  *       case Success(v) =>
@@ -47,7 +48,7 @@ import scala.language.implicitConversions
  * catching exceptions along the way. The `flatMap` and `map` combinators in the above example each essentially
  * pass off either their successfully completed value, wrapped in the `Success` type for it to be further operated
  * upon by the next combinator in the chain, or the exception wrapped in the `Failure` type usually to be simply
- * passed on down the chain. Combinators such as `rescue` and `recover` are designed to provide some type of
+ * passed on down the chain. Combinators such as `recover` and `recoverWith` are designed to provide some type of
  * default behavior in the case of failure.
  *
  * ''Note'': only non-fatal exceptions are caught by the combinators on `Try` (see [[scala.util.control.NonFatal]]).