{"action":"created","comment":{"url":"https://api.github.com/repos/scala/scala/pulls/comments/31571968","id":31571968,"diff_hunk":"@@ -9,518 +9,276 @@\n package scala\n package util\n \n-import scala.reflect.{ ClassTag, classTag }\n-import scala.math.{ Ordering, max, min }\n+import scala.reflect.ClassTag\n+import scala.math.Ordering\n \n-/** The Sorting object provides functions that can sort various kinds of\n-  * objects. You can provide a comparison function, or you can request a sort\n-  * of items that are viewable as [[scala.math.Ordered]]. Some sorts that\n-  * operate directly on a subset of value types are also provided. These\n-  * implementations are derived from those in the Sun JDK.\n+/** The `Sorting` object provides convenience wrappers for `java.util.Arrays.sort`.\n+  * Methods that defer to `java.util.Arrays.sort` say that they do or under what\n+  * conditions that they do.\n   *\n-  * Note that stability doesn't matter for value types, so use the `quickSort`\n-  * variants for those. `stableSort` is intended to be used with\n-  * objects when the prior ordering should be preserved, where possible.\n+  * `Sorting` also implements a general-purpose quicksort and stable (merge) sort\n+  * for those cases where `java.util.Arrays.sort` could only be used at the cost\n+  * of a large memory penalty.  If performance rather than memory usage is the\n+  * primary concern, one may wish to find alternate strategies to use\n+  * `java.util.Arrays.sort` directly e.g. by boxing primitives to use\n+  * a custom ordering on them.\n+  *\n+  * `Sorting` provides methods where you can provide a comparison function, or\n+  * can request a sort of items that are [[scala.math.Ordered]] or that\n+  * otherwise have an implicit or explicit [[scala.math.Ordering]].\n+  *\n+  * Note also that high-performance non-default sorts for numeric types\n+  * are not provided.  If this is required, it is advisable to investigate\n+  * other libraries that cover this use case.\n   *\n   * @author  Ross Judson\n-  * @version 1.0\n+  * @author  Adriaan Moors\n+  * @author  Rex Kerr\n+  * @version 1.1\n   */\n object Sorting {\n-  /** Quickly sort an array of Doubles. */\n-  def quickSort(a: Array[Double]) { sort1(a, 0, a.length) }\n-\n-  /** Quickly sort an array of items with an implicit Ordering. */\n-  def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) }\n-\n-  /** Quickly sort an array of Ints. */\n-  def quickSort(a: Array[Int]) { sort1(a, 0, a.length) }\n-\n-  /** Quickly sort an array of Floats. */\n-  def quickSort(a: Array[Float]) { sort1(a, 0, a.length) }\n-\n-  /** Sort an array of K where K is Ordered, preserving the existing order\n-    * where the values are equal. */\n-  def stableSort[K: ClassTag: Ordering](a: Array[K]) {\n-    stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _)\n-  }\n+  /** Sort an array of Doubles using `java.util.Arrays.sort`. */\n+  def quickSort(a: Array[Double]): Unit = java.util.Arrays.sort(a)\n \n-  /** Sorts an array of `K` given an ordering function `f`.\n-   *  `f` should return `true` iff its first parameter is strictly less than its second parameter.\n-   */\n-  def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean) {\n-    stableSort(a, 0, a.length-1, new Array[K](a.length), f)\n-  }\n+  /** Sort an array of Ints using `java.util.Arrays.sort`. */\n+  def quickSort(a: Array[Int]): Unit    = java.util.Arrays.sort(a)\n \n-  /** Sorts an arbitrary sequence into an array, given a comparison function\n-   *  that should return `true` iff parameter one is strictly less than parameter two.\n-   *\n-   *  @param  a the sequence to be sorted.\n-   *  @param  f the comparison function.\n-   *  @return the sorted sequence of items.\n-   */\n-  def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = {\n-    val ret = a.toArray\n-    stableSort(ret, f)\n-    ret\n-  }\n+  /** Sort an array of Floats using `java.util.Arrays.sort`. */\n+  def quickSort(a: Array[Float]): Unit  = java.util.Arrays.sort(a)\n+  \n+  private final val qsortThreshold = 16\n \n-  /** Sorts an arbitrary sequence of items that are viewable as ordered. */\n-  def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] =\n-    stableSort(a, Ordering[K].lt _)\n-\n-  /** Stably sorts a sequence of items given an extraction function that will\n-   *  return an ordered key from an item.\n-   *\n-   *  @param  a the sequence to be sorted.\n-   *  @param  f the comparison function.\n-   *  @return the sorted sequence of items.\n-   */\n-  def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] =\n-    stableSort(a)(implicitly[ClassTag[K]], Ordering[M] on f)\n-\n-  private def sort1[K: Ordering](x: Array[K], off: Int, len: Int) {\n-    val ord = Ordering[K]\n-    import ord._\n-\n-    def swap(a: Int, b: Int) {\n-      val t = x(a)\n-      x(a) = x(b)\n-      x(b) = t\n-    }\n-    def vecswap(_a: Int, _b: Int, n: Int) {\n-      var a = _a\n-      var b = _b\n-      var i = 0\n-      while (i < n) {\n-        swap(a, b)\n-        i += 1\n-        a += 1\n-        b += 1\n-      }\n-    }\n-    def med3(a: Int, b: Int, c: Int) = {\n-      if (x(a) < x(b)) {\n-        if (x(b) < x(c)) b else if (x(a) < x(c)) c else a\n-      } else {\n-        if (x(b) > x(c)) b else if (x(a) > x(c)) c else a\n-      }\n-    }\n-    def sort2(off: Int, len: Int) {\n-      // Insertion sort on smallest arrays\n-      if (len < 7) {\n-        var i = off\n-        while (i < len + off) {\n-          var j = i\n-          while (j > off && x(j-1) > x(j)) {\n-            swap(j, j-1)\n-            j -= 1\n+  /** Sort array `a` with quicksort, using the Ordering on its elements.\n+    * This algorithm sorts in place, so no additional memory is used aside from\n+    * what might be required to box individual elements during comparison.\n+    */\n+  def quickSort[K: Ordering](a: Array[K]): Unit = {\n+    // Must have iN >= i0 or math will fail.  Also, i0 >= 0.\n+    def inner(a: Array[K], i0: Int, iN: Int, ord: Ordering[K]): Unit = {\n+      if (iN - i0 < qsortThreshold) insertionSort(a, i0, iN, ord)\n+      else {\n+        var iK = (i0 + iN) >>> 1    // Unsigned div by 2\n+        // Find index of median of first, central, and last elements\n+        var pL = \n+          if (ord.compare(a(i0), a(iN - 1)) <= 0)\n+            if (ord.compare(a(i0), a(iK)) < 0)\n+              if (ord.compare(a(iN - 1), a(iK)) < 0) iN - 1 else iK\n+            else i0\n+          else\n+            if (ord.compare(a(i0), a(iK)) < 0) i0\n+            else\n+              if (ord.compare(a(iN - 1), a(iK)) <= 0) iN - 1\n+              else iK\n+        val pivot = a(pL)\n+        // pL is the start of the pivot block; move it into the middle if needed\n+        if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK }\n+        // Elements equal to the pivot will be in range pL until pR\n+        var pR = pL + 1\n+        // Items known to be less than pivot are below iA (range i0 until iA)\n+        var iA = i0\n+        // Items known to be greater than pivot are at or above iB (range iB until iN)\n+        var iB = iN\n+        // Scan through everything in the buffer before the pivot(s)\n+        while (pL - iA > 0) {\n+          val current = a(iA)\n+          ord.compare(current, pivot) match {\n+            case 0 =>\n+              // Swap current out with pivot block\n+              a(iA) = a(pL - 1)\n+              a(pL - 1) = current\n+              pL -= 1\n+            case x if x < 0 =>\n+              // Already in place.  Just update indicies.\n+              iA += 1\n+            case _ if iB > pR =>\n+              // Wrong side.  There's room on the other side, so swap\n+              a(iA) = a(iB - 1)\n+              a(iB - 1) = current\n+              iB -= 1\n+            case _ =>\n+              // Wrong side and there is no room.  Swap by rotating pivot block.\n+              a(iA) = a(pL - 1)\n+              a(pL - 1) = a(pR - 1)\n+              a(pR - 1) = current\n+              pL -= 1\n+              pR -= 1\n+              iB -= 1\n           }\n-          i += 1\n         }\n-      } else {\n-        // Choose a partition element, v\n-        var m = off + (len >> 1)        // Small arrays, middle element\n-        if (len > 7) {\n-          var l = off\n-          var n = off + len - 1\n-          if (len > 40) {        // Big arrays, pseudomedian of 9\n-            val s = len / 8\n-            l = med3(l, l+s, l+2*s)\n-            m = med3(m-s, m, m+s)\n-            n = med3(n-2*s, n-s, n)\n+        // Get anything remaining in buffer after the pivot(s)\n+        while (iB - pR > 0) {\n+          val current = a(iB - 1)\n+          ord.compare(current, pivot) match {\n+            case 0 =>\n+              // Swap current out with pivot block\n+              a(iB - 1) = a(pR)\n+              a(pR) = current\n+              pR += 1\n+            case x if x > 0 =>\n+              // Already in place.  Just update indices.\n+              iB -= 1\n+            case _ =>\n+              // Wrong side and we already know there is no room.  Swap by rotating pivot block.\n+              a(iB - 1) = a(pR)\n+              a(pR) = a(pL)\n+              a(pL) = current\n+              iA += 1\n+              pL += 1\n+              pR += 1\n           }\n-          m = med3(l, m, n) // Mid-size, med of 3\n         }\n-        val v = x(m)\n-\n-        // Establish Invariant: v* (<v)* (>v)* v*\n-        var a = off\n-        var b = a\n-        var c = off + len - 1\n-        var d = c\n-        var done = false\n-        while (!done) {\n-          while (b <= c && x(b) <= v) {\n-            if (x(b) equiv v) {\n-              swap(a, b)\n-              a += 1\n-            }\n-            b += 1\n-          }\n-          while (c >= b && x(c) >= v) {\n-            if (x(c) equiv v) {\n-              swap(c, d)\n-              d -= 1\n-            }\n-            c -= 1\n-          }\n-          if (b > c) {\n-            done = true\n-          } else {\n-            swap(b, c)\n-            c -= 1\n-            b += 1\n-          }\n+        // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen\n+        if (iA - i0 < iN - iB) {\n+          inner(a, i0, iA, ord)  // True recursion\n+          inner(a, iB, iN, ord)  // Should be tail recursion\n+        }\n+        else {\n+          inner(a, iB, iN, ord)  // True recursion\n+          inner(a, i0, iA, ord)  // Should be tail recursion\n         }\n-\n-        // Swap partition elements back to middle\n-        val n = off + len\n-        var s = math.min(a-off, b-a)\n-        vecswap(off, b-s, s)\n-        s = math.min(d-c, n-d-1)\n-        vecswap(b,   n-s, s)\n-\n-        // Recursively sort non-partition-elements\n-        s = b - a\n-        if (s > 1)\n-          sort2(off, s)\n-        s = d - c\n-        if (s > 1)\n-          sort2(n-s, s)\n       }\n     }\n-    sort2(off, len)\n+    inner(a, 0, a.length, implicitly[Ordering[K]])\n   }\n-\n-  private def sort1(x: Array[Int], off: Int, len: Int) {\n-    def swap(a: Int, b: Int) {\n-      val t = x(a)\n-      x(a) = x(b)\n-      x(b) = t\n+  \n+  private final val mergeThreshold = 32\n+  \n+  // Ordering[T] might be slow especially for boxed primitives, so use binary search variant of insertion sort\n+  // Caller must pass iN >= i0 or math will fail.  Also, i0 >= 0.\n+  private def insertionSort[@specialized T](a: Array[T], i0: Int, iN: Int, ord: Ordering[T]): Unit = {\n+    val n = iN - i0\n+    if (n < 2) return\n+    if (ord.compare(a(i0), a(i0+1)) > 0) {\n+      val temp = a(i0)\n+      a(i0) = a(i0+1)\n+      a(i0+1) = temp\n     }\n-    def vecswap(_a: Int, _b: Int, n: Int) {\n-      var a = _a\n-      var b = _b\n-      var i = 0\n-      while (i < n) {\n-        swap(a, b)\n-        i += 1\n-        a += 1\n-        b += 1\n-      }\n-    }\n-    def med3(a: Int, b: Int, c: Int) = {\n-      if (x(a) < x(b)) {\n-        if (x(b) < x(c)) b else if (x(a) < x(c)) c else a\n-      } else {\n-        if (x(b) > x(c)) b else if (x(a) > x(c)) c else a\n-      }\n-    }\n-    def sort2(off: Int, len: Int) {\n-      // Insertion sort on smallest arrays\n-      if (len < 7) {\n-        var i = off\n-        while (i < len + off) {\n-          var j = i\n-          while (j>off && x(j-1) > x(j)) {\n-            swap(j, j-1)\n-            j -= 1\n-          }\n-          i += 1\n+    var m = 2\n+    while (m < n) {\n+      // Speed up already-sorted case by checking last element first\n+      val next = a(i0 + m)\n+      if (ord.compare(next, a(i0+m-1)) < 0) {\n+        var iA = i0\n+        var iB = i0 + m - 1\n+        while (iB - iA > 1) {\n+          val ix = (iA + iB) >>> 1    // Use bit shift to get unsigned div by 2\n+          if (ord.compare(next, a(ix)) < 0) iB = ix\n+          else iA = ix\n         }\n-      } else {\n-        // Choose a partition element, v\n-        var m = off + (len >> 1)        // Small arrays, middle element\n-        if (len > 7) {\n-          var l = off\n-          var n = off + len - 1\n-          if (len > 40) {        // Big arrays, pseudomedian of 9\n-            val s = len / 8\n-            l = med3(l, l+s, l+2*s)\n-            m = med3(m-s, m, m+s)\n-            n = med3(n-2*s, n-s, n)\n-          }\n-          m = med3(l, m, n) // Mid-size, med of 3\n-        }\n-        val v = x(m)\n-\n-        // Establish Invariant: v* (<v)* (>v)* v*\n-        var a = off\n-        var b = a\n-        var c = off + len - 1\n-        var d = c\n-        var done = false\n-        while (!done) {\n-          while (b <= c && x(b) <= v) {\n-            if (x(b) == v) {\n-              swap(a, b)\n-              a += 1\n-            }\n-            b += 1\n-          }\n-          while (c >= b && x(c) >= v) {\n-            if (x(c) == v) {\n-              swap(c, d)\n-              d -= 1\n-            }\n-            c -= 1\n-          }\n-          if (b > c) {\n-            done = true\n-          } else {\n-            swap(b, c)\n-            c -= 1\n-            b += 1\n-          }\n+        val ix = iA + (if (ord.compare(next, a(iA)) < 0) 0 else 1)\n+        var i = i0 + m\n+        while (i > ix) {\n+          a(i) = a(i-1)\n+          i -= 1\n         }\n-\n-        // Swap partition elements back to middle\n-        val n = off + len\n-        var s = math.min(a-off, b-a)\n-        vecswap(off, b-s, s)\n-        s = math.min(d-c, n-d-1)\n-        vecswap(b,   n-s, s)\n-\n-        // Recursively sort non-partition-elements\n-        s = b - a\n-        if (s > 1)\n-          sort2(off, s)\n-        s = d - c\n-        if (s > 1)\n-          sort2(n-s, s)\n+        a(ix) = next\n       }\n+      m += 1\n     }\n-    sort2(off, len)\n   }\n-\n-  private def sort1(x: Array[Double], off: Int, len: Int) {\n-    def swap(a: Int, b: Int) {\n-      val t = x(a)\n-      x(a) = x(b)\n-      x(b) = t\n+  \n+  // Caller is required to pass iN >= i0, else math will fail.  Also, i0 >= 0.\n+  private def mergeSort[@specialized T: ClassTag](a: Array[T], i0: Int, iN: Int, ord: Ordering[T], scratch: Array[T] = null): Unit = {\n+    if (iN - i0 < mergeThreshold) insertionSort(a, i0, iN, ord)\n+    else {\n+      val iK = (i0 + iN) >>> 1   // Bit shift equivalent to unsigned math, no overflow\n+      val sc = if (scratch eq null) new Array[T](iK - i0) else scratch\n+      mergeSort(a, i0, iK, ord, sc)\n+      mergeSort(a, iK, iN, ord, sc)\n+      mergeSorted(a, i0, iK, iN, ord, sc)\n     }\n-    def vecswap(_a: Int, _b: Int, n: Int) {\n-      var a = _a\n-      var b = _b\n-      var i = 0\n-      while (i < n) {\n-        swap(a, b)\n+  }\n+  \n+  // Must have 0 <= i0 < iK < iN\n+  private def mergeSorted[@specialized T](a: Array[T], i0: Int, iK: Int, iN: Int, ord: Ordering[T], scratch: Array[T]): Unit = {\n+    // Check to make sure we're not already in order\n+    if (ord.compare(a(iK-1), a(iK)) > 0) {\n+      var i = i0\n+      val jN = iK - i0\n+      var j = 0\n+      while (i < iK) {\n+        scratch (j) = a(i)\n         i += 1\n-        a += 1\n-        b += 1\n-      }\n-    }\n-    def med3(a: Int, b: Int, c: Int) = {\n-      val ab = x(a) compare x(b)\n-      val bc = x(b) compare x(c)\n-      val ac = x(a) compare x(c)\n-      if (ab < 0) {\n-        if (bc < 0) b else if (ac < 0) c else a\n-      } else {\n-        if (bc > 0) b else if (ac > 0) c else a\n+        j += 1\n       }\n-    }\n-    def sort2(off: Int, len: Int) {\n-      // Insertion sort on smallest arrays\n-      if (len < 7) {\n-        var i = off\n-        while (i < len + off) {\n-          var j = i\n-          while (j > off && (x(j-1) compare x(j)) > 0) {\n-            swap(j, j-1)\n-            j -= 1\n-          }\n-          i += 1\n-        }\n-      } else {\n-        // Choose a partition element, v\n-        var m = off + (len >> 1)        // Small arrays, middle element\n-        if (len > 7) {\n-          var l = off\n-          var n = off + len - 1\n-          if (len > 40) {        // Big arrays, pseudomedian of 9\n-            val s = len / 8\n-            l = med3(l, l+s, l+2*s)\n-            m = med3(m-s, m, m+s)\n-            n = med3(n-2*s, n-s, n)\n-          }\n-          m = med3(l, m, n) // Mid-size, med of 3\n-        }\n-        val v = x(m)\n-\n-        // Establish Invariant: v* (<v)* (>v)* v*\n-        var a = off\n-        var b = a\n-        var c = off + len - 1\n-        var d = c\n-        var done = false\n-        while (!done) {\n-          var bv = x(b) compare v\n-          while (b <= c && bv <= 0) {\n-            if (bv == 0) {\n-              swap(a, b)\n-              a += 1\n-            }\n-            b += 1\n-            if (b <= c) bv = x(b) compare v\n-          }\n-          var cv = x(c) compare v\n-          while (c >= b && cv >= 0) {\n-            if (cv == 0) {\n-              swap(c, d)\n-              d -= 1\n-            }\n-            c -= 1\n-            if (c >= b) cv = x(c) compare v\n-          }\n-          if (b > c) {\n-            done = true\n-          } else {\n-            swap(b, c)\n-            c -= 1\n-            b += 1\n-          }\n-        }\n-\n-        // Swap partition elements back to middle\n-        val n = off + len\n-        var s = math.min(a-off, b-a)\n-        vecswap(off, b-s, s)\n-        s = math.min(d-c, n-d-1)\n-        vecswap(b,   n-s, s)\n-\n-        // Recursively sort non-partition-elements\n-        s = b - a\n-        if (s > 1)\n-          sort2(off, s)\n-        s = d - c\n-        if (s > 1)\n-          sort2(n-s, s)\n+      var k = i0\n+      j = 0\n+      while (i < iN && j < jN) {\n+        if (ord.compare(a(i), scratch(j)) < 0) { a(k) = a(i); i += 1 }\n+        else { a(k) = scratch(j); j += 1 }\n+        k += 1\n       }\n+      while (j < jN) { a(k) = scratch(j); j += 1; k += 1 }\n+      // Don't need to finish a(i) because it's already in place, k = i\n     }\n-    sort2(off, len)\n   }\n-\n-  private def sort1(x: Array[Float], off: Int, len: Int) {\n-    def swap(a: Int, b: Int) {\n-      val t = x(a)\n-      x(a) = x(b)\n-      x(b) = t\n+  \n+  // Why would you even do this?\n+  private def booleanSort(a: Array[Boolean]): Unit = {\n+    var i = 0\n+    var n = 0\n+    while (i < a.length) {","path":"src/library/scala/util/Sorting.scala","position":578,"original_position":578,"commit_id":"9aae16aa231ad64e3987aaad2a206beaf10c76e0","original_commit_id":"9aae16aa231ad64e3987aaad2a206beaf10c76e0","user":{"login":"Arneball","id":2081988,"avatar_url":"https://avatars.githubusercontent.com/u/2081988?v=3","gravatar_id":"","url":"https://api.github.com/users/Arneball","html_url":"https://github.com/Arneball","followers_url":"https://api.github.com/users/Arneball/followers","following_url":"https://api.github.com/users/Arneball/following{/other_user}","gists_url":"https://api.github.com/users/Arneball/gists{/gist_id}","starred_url":"https://api.github.com/users/Arneball/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Arneball/subscriptions","organizations_url":"https://api.github.com/users/Arneball/orgs","repos_url":"https://api.github.com/users/Arneball/repos","events_url":"https://api.github.com/users/Arneball/events{/privacy}","received_events_url":"https://api.github.com/users/Arneball/received_events","type":"User","site_admin":false},"body":"Wouldn't it be beneficial to pull out a.length in a local variable so that we don't need to do ```arraylength``` in every iteration?","created_at":"2015-06-02T21:14:21Z","updated_at":"2015-06-02T21:14:21Z","html_url":"https://github.com/scala/scala/pull/4534#discussion_r31571968","pull_request_url":"https://api.github.com/repos/scala/scala/pulls/4534","_links":{"self":{"href":"https://api.github.com/repos/scala/scala/pulls/comments/31571968"},"html":{"href":"https://github.com/scala/scala/pull/4534#discussion_r31571968"},"pull_request":{"href":"https://api.github.com/repos/scala/scala/pulls/4534"}}},"pull_request":{"url":"https://api.github.com/repos/scala/scala/pulls/4534","id":36578176,"html_url":"https://github.com/scala/scala/pull/4534","diff_url":"https://github.com/scala/scala/pull/4534.diff","patch_url":"https://github.com/scala/scala/pull/4534.patch","issue_url":"https://api.github.com/repos/scala/scala/issues/4534","number":4534,"state":"open","locked":false,"title":"Clean implementation of sorts for scala.util.Sorting.","user":{"login":"Ichoran","id":2298644,"avatar_url":"https://avatars.githubusercontent.com/u/2298644?v=3","gravatar_id":"","url":"https://api.github.com/users/Ichoran","html_url":"https://github.com/Ichoran","followers_url":"https://api.github.com/users/Ichoran/followers","following_url":"https://api.github.com/users/Ichoran/following{/other_user}","gists_url":"https://api.github.com/users/Ichoran/gists{/gist_id}","starred_url":"https://api.github.com/users/Ichoran/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Ichoran/subscriptions","organizations_url":"https://api.github.com/users/Ichoran/orgs","repos_url":"https://api.github.com/users/Ichoran/repos","events_url":"https://api.github.com/users/Ichoran/events{/privacy}","received_events_url":"https://api.github.com/users/Ichoran/received_events","type":"User","site_admin":false},"body":"Removed code based on Sun JDK sorts and implemented new (basic) sorts from\r\nscratch.  Deferred to Java Arrays.sort whenever practical.  Behavior of\r\n`scala.util.Sorting` should be unchanged, but changed documentation to\r\nspecify when the Java methods are being used (as they're typically very fast).\r\n\r\nA JUnit test is provided.\r\n\r\nPerformance is important for sorts.  Everything is better with this patch,\r\nthough it could be better yet, as described below.\r\n\r\nBelow are sort times (in microseconds, SEM < 5%) for various 1024-element\r\narrays of small case classes that compare on an int field (quickSort), or\r\nint arrays that use custom ordering (stableSort).  Note: \"degenerate\"\r\nmeans there are only 16 values possible, so there are lots of ties.\r\nTimes are all with fresh data (no re-using cache from run to run).\r\n\r\nResults:\r\n\r\n```\r\n                        random  sorted  reverse  degenerate  big:64k  tiny:16\r\nOld Sorting.quickSort     234     181      178         103    25,700      1.4\r\nNew Sorting.quickSort     170      27      115          74    18,600      0.8\r\n\r\nOld Sorting.stableSort    321     234      236         282    32,600      2.1\r\nNew Sorting.stableSort    239      16      194         194    25,100      1.2\r\n\r\njava.util.Arrays.sort     124       4        8         105    13,500      0.8\r\njava.util.Arrays.sort|Box 126      15       13         112    13,200      0.9\r\n```\r\n\r\nThe 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.\r\n\r\nA snapshot of some of my benchmarking code is below.\r\n\r\n(Yes, lots of repeating myself--it's dangerous not to when trying to get\r\nsomewhat accurate benchmarks.)\r\n\r\n```\r\nimport java.util.Arrays\r\nimport java.util.Comparator\r\nimport math.Ordering\r\nimport util.Sorting\r\nimport reflect.ClassTag\r\n\r\nval th = ichi.bench.Thyme.warmed()\r\n\r\ncase class N(i: Int, j: Int) {}\r\nval a = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt, i)) )\r\nvar ai = 0\r\nval b = Array.fill(1024)( Array.tabulate(1024)(i => N(i, i)) )\r\nvar bi = 0\r\nval c = Array.fill(1024)( Array.tabulate(1024)(i => N(1024-i, i)) )\r\nvar ci = 0\r\nval d = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt(16), i)) )\r\nvar di = 0\r\nval e = Array.fill(16)( Array.tabulate(65536)(i => N(util.Random.nextInt, i)) )\r\nvar ei = 0\r\nval f = Array.fill(65535)( Array.tabulate(16)(i => N(util.Random.nextInt, i)) )\r\nvar fi = 0\r\n\r\nval 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 }\r\nfor (s <- Seq(\"one\", \"two\", \"three\")) {\r\n  println(s)\r\n  th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n  th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n  th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n  th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n  th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n  th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Sorting.quickSort(x)(o); x(x.length/3) }\r\n}\r\n\r\ndef ix(ns: Array[N]) = {\r\n  val is = new Array[Int](ns.length)\r\n  var i = 0\r\n  while (i < ns.length) {\r\n    is(i) = ns(i).i\r\n    i += 1\r\n  }\r\n  is\r\n}\r\nval p = new Ordering[Int]{ def compare(a: Int, b: Int) = if (a > b) 1 else if (a < b) -1 else 0 }\r\nfor (s <- Seq(\"one\", \"two\", \"three\")) {\r\n  println(s)\r\n  val tag: ClassTag[Int] = implicitly[ClassTag[Int]]\r\n  th.pbench{ val x = ix(a(ai)); ai = (ai+1)%a.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n  th.pbench{ val x = ix(b(bi)); bi = (bi+1)%b.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n  th.pbench{ val x = ix(c(ci)); ci = (ci+1)%c.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n  th.pbench{ val x = ix(d(di)); di = (di+1)%d.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n  th.pbench{ val x = ix(e(ei)); ei = (ei+1)%e.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n  th.pbench{ val x = ix(f(fi)); fi = (fi+1)%f.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }\r\n}\r\n\r\nfor (s <- Seq(\"one\", \"two\", \"three\")) {\r\n  println(s)\r\n  th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Arrays.sort(x, o); x(x.length/3) }\r\n  th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Arrays.sort(x, o); x(x.length/3) }\r\n  th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Arrays.sort(x, o); x(x.length/3) }\r\n  th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Arrays.sort(x, o); x(x.length/3) }\r\n  th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Arrays.sort(x, o); x(x.length/3) }\r\n  th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Arrays.sort(x, o); x(x.length/3) }\r\n}\r\n\r\ndef bx(is: Array[Int]): Array[java.lang.Integer] = {\r\n  val Is = new Array[java.lang.Integer](is.length)\r\n  var i = 0\r\n  while (i < is.length) {\r\n    Is(i) = java.lang.Integer.valueOf(is(i))\r\n    i += 1\r\n  }\r\n  Is\r\n}\r\ndef xb(Is: Array[java.lang.Integer]): Array[Int] = {\r\n  val is = new Array[Int](Is.length)\r\n  var i = 0\r\n  while (i < is.length) {\r\n    is(i) = Is(i).intValue\r\n    i += 1\r\n  }\r\n  is\r\n}\r\nval q = new Comparator[java.lang.Integer]{\r\n  def compare(a: java.lang.Integer, b: java.lang.Integer) = o.compare(a.intValue, b.intValue)\r\n}\r\nfor (s <- Seq(\"one\", \"two\", \"three\")) {\r\n  println(s)\r\n  val tag: ClassTag[Int] = implicitly[ClassTag[Int]]\r\n  th.pbench{ val x = bx(ix(a(ai))); ai = (ai+1)%a.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n  th.pbench{ val x = bx(ix(b(bi))); bi = (bi+1)%b.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n  th.pbench{ val x = bx(ix(c(ci))); ci = (ci+1)%c.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n  th.pbench{ val x = bx(ix(d(di))); di = (di+1)%d.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n  th.pbench{ val x = bx(ix(e(ei))); ei = (ei+1)%e.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n  th.pbench{ val x = bx(ix(f(fi))); fi = (fi+1)%f.length; Arrays.sort(x, q); xb(x)(x.length/3) }\r\n}\r\n```","created_at":"2015-05-31T07:18:14Z","updated_at":"2015-06-02T21:14:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"681818ab9dc15700fad11947547ce0b376d43b08","assignee":null,"milestone":{"url":"https://api.github.com/repos/scala/scala/milestones/48","html_url":"https://github.com/scala/scala/milestones/2.11.7","labels_url":"https://api.github.com/repos/scala/scala/milestones/48/labels","id":985497,"number":48,"title":"2.11.7","description":"Merge to 2.11.x.\r\n","creator":{"login":"adriaanm","id":91083,"avatar_url":"https://avatars.githubusercontent.com/u/91083?v=3","gravatar_id":"","url":"https://api.github.com/users/adriaanm","html_url":"https://github.com/adriaanm","followers_url":"https://api.github.com/users/adriaanm/followers","following_url":"https://api.github.com/users/adriaanm/following{/other_user}","gists_url":"https://api.github.com/users/adriaanm/gists{/gist_id}","starred_url":"https://api.github.com/users/adriaanm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/adriaanm/subscriptions","organizations_url":"https://api.github.com/users/adriaanm/orgs","repos_url":"https://api.github.com/users/adriaanm/repos","events_url":"https://api.github.com/users/adriaanm/events{/privacy}","received_events_url":"https://api.github.com/users/adriaanm/received_events","type":"User","site_admin":false},"open_issues":13,"closed_issues":125,"state":"open","created_at":"2015-02-19T00:12:20Z","updated_at":"2015-06-02T05:34:02Z","due_on":"2015-06-30T22:00:00Z","closed_at":null},"commits_url":"https://api.github.com/repos/scala/scala/pulls/4534/commits","review_comments_url":"https://api.github.com/repos/scala/scala/pulls/4534/comments","review_comment_url":"https://api.github.com/repos/scala/scala/pulls/comments{/number}","comments_url":"https://api.github.com/repos/scala/scala/issues/4534/comments","statuses_url":"https://api.github.com/repos/scala/scala/statuses/9aae16aa231ad64e3987aaad2a206beaf10c76e0","head":{"label":"Ichoran:sorting-reimpl","ref":"sorting-reimpl","sha":"9aae16aa231ad64e3987aaad2a206beaf10c76e0","user":{"login":"Ichoran","id":2298644,"avatar_url":"https://avatars.githubusercontent.com/u/2298644?v=3","gravatar_id":"","url":"https://api.github.com/users/Ichoran","html_url":"https://github.com/Ichoran","followers_url":"https://api.github.com/users/Ichoran/followers","following_url":"https://api.github.com/users/Ichoran/following{/other_user}","gists_url":"https://api.github.com/users/Ichoran/gists{/gist_id}","starred_url":"https://api.github.com/users/Ichoran/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Ichoran/subscriptions","organizations_url":"https://api.github.com/users/Ichoran/orgs","repos_url":"https://api.github.com/users/Ichoran/repos","events_url":"https://api.github.com/users/Ichoran/events{/privacy}","received_events_url":"https://api.github.com/users/Ichoran/received_events","type":"User","site_admin":false},"repo":{"id":12699333,"name":"scala","full_name":"Ichoran/scala","owner":{"login":"Ichoran","id":2298644,"avatar_url":"https://avatars.githubusercontent.com/u/2298644?v=3","gravatar_id":"","url":"https://api.github.com/users/Ichoran","html_url":"https://github.com/Ichoran","followers_url":"https://api.github.com/users/Ichoran/followers","following_url":"https://api.github.com/users/Ichoran/following{/other_user}","gists_url":"https://api.github.com/users/Ichoran/gists{/gist_id}","starred_url":"https://api.github.com/users/Ichoran/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Ichoran/subscriptions","organizations_url":"https://api.github.com/users/Ichoran/orgs","repos_url":"https://api.github.com/users/Ichoran/repos","events_url":"https://api.github.com/users/Ichoran/events{/privacy}","received_events_url":"https://api.github.com/users/Ichoran/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Ichoran/scala","description":"The Scala programming language","fork":true,"url":"https://api.github.com/repos/Ichoran/scala","forks_url":"https://api.github.com/repos/Ichoran/scala/forks","keys_url":"https://api.github.com/repos/Ichoran/scala/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Ichoran/scala/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Ichoran/scala/teams","hooks_url":"https://api.github.com/repos/Ichoran/scala/hooks","issue_events_url":"https://api.github.com/repos/Ichoran/scala/issues/events{/number}","events_url":"https://api.github.com/repos/Ichoran/scala/events","assignees_url":"https://api.github.com/repos/Ichoran/scala/assignees{/user}","branches_url":"https://api.github.com/repos/Ichoran/scala/branches{/branch}","tags_url":"https://api.github.com/repos/Ichoran/scala/tags","blobs_url":"https://api.github.com/repos/Ichoran/scala/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Ichoran/scala/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Ichoran/scala/git/refs{/sha}","trees_url":"https://api.github.com/repos/Ichoran/scala/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Ichoran/scala/statuses/{sha}","languages_url":"https://api.github.com/repos/Ichoran/scala/languages","stargazers_url":"https://api.github.com/repos/Ichoran/scala/stargazers","contributors_url":"https://api.github.com/repos/Ichoran/scala/contributors","subscribers_url":"https://api.github.com/repos/Ichoran/scala/subscribers","subscription_url":"https://api.github.com/repos/Ichoran/scala/subscription","commits_url":"https://api.github.com/repos/Ichoran/scala/commits{/sha}","git_commits_url":"https://api.github.com/repos/Ichoran/scala/git/commits{/sha}","comments_url":"https://api.github.com/repos/Ichoran/scala/comments{/number}","issue_comment_url":"https://api.github.com/repos/Ichoran/scala/issues/comments{/number}","contents_url":"https://api.github.com/repos/Ichoran/scala/contents/{+path}","compare_url":"https://api.github.com/repos/Ichoran/scala/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Ichoran/scala/merges","archive_url":"https://api.github.com/repos/Ichoran/scala/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Ichoran/scala/downloads","issues_url":"https://api.github.com/repos/Ichoran/scala/issues{/number}","pulls_url":"https://api.github.com/repos/Ichoran/scala/pulls{/number}","milestones_url":"https://api.github.com/repos/Ichoran/scala/milestones{/number}","notifications_url":"https://api.github.com/repos/Ichoran/scala/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Ichoran/scala/labels{/name}","releases_url":"https://api.github.com/repos/Ichoran/scala/releases{/id}","created_at":"2013-09-09T10:59:11Z","updated_at":"2014-06-29T21:55:23Z","pushed_at":"2015-06-02T00:58:35Z","git_url":"git://github.com/Ichoran/scala.git","ssh_url":"git@github.com:Ichoran/scala.git","clone_url":"https://github.com/Ichoran/scala.git","svn_url":"https://github.com/Ichoran/scala","homepage":"http://www.scala-lang.org/","size":89544,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"scala:2.11.x","ref":"2.11.x","sha":"70f0b1ded880ec9b3a9478d02f1898fcfeee230c","user":{"login":"scala","id":57059,"avatar_url":"https://avatars.githubusercontent.com/u/57059?v=3","gravatar_id":"","url":"https://api.github.com/users/scala","html_url":"https://github.com/scala","followers_url":"https://api.github.com/users/scala/followers","following_url":"https://api.github.com/users/scala/following{/other_user}","gists_url":"https://api.github.com/users/scala/gists{/gist_id}","starred_url":"https://api.github.com/users/scala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scala/subscriptions","organizations_url":"https://api.github.com/users/scala/orgs","repos_url":"https://api.github.com/users/scala/repos","events_url":"https://api.github.com/users/scala/events{/privacy}","received_events_url":"https://api.github.com/users/scala/received_events","type":"Organization","site_admin":false},"repo":{"id":2888818,"name":"scala","full_name":"scala/scala","owner":{"login":"scala","id":57059,"avatar_url":"https://avatars.githubusercontent.com/u/57059?v=3","gravatar_id":"","url":"https://api.github.com/users/scala","html_url":"https://github.com/scala","followers_url":"https://api.github.com/users/scala/followers","following_url":"https://api.github.com/users/scala/following{/other_user}","gists_url":"https://api.github.com/users/scala/gists{/gist_id}","starred_url":"https://api.github.com/users/scala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scala/subscriptions","organizations_url":"https://api.github.com/users/scala/orgs","repos_url":"https://api.github.com/users/scala/repos","events_url":"https://api.github.com/users/scala/events{/privacy}","received_events_url":"https://api.github.com/users/scala/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scala/scala","description":"The Scala programming language","fork":false,"url":"https://api.github.com/repos/scala/scala","forks_url":"https://api.github.com/repos/scala/scala/forks","keys_url":"https://api.github.com/repos/scala/scala/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scala/scala/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scala/scala/teams","hooks_url":"https://api.github.com/repos/scala/scala/hooks","issue_events_url":"https://api.github.com/repos/scala/scala/issues/events{/number}","events_url":"https://api.github.com/repos/scala/scala/events","assignees_url":"https://api.github.com/repos/scala/scala/assignees{/user}","branches_url":"https://api.github.com/repos/scala/scala/branches{/branch}","tags_url":"https://api.github.com/repos/scala/scala/tags","blobs_url":"https://api.github.com/repos/scala/scala/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scala/scala/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scala/scala/git/refs{/sha}","trees_url":"https://api.github.com/repos/scala/scala/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scala/scala/statuses/{sha}","languages_url":"https://api.github.com/repos/scala/scala/languages","stargazers_url":"https://api.github.com/repos/scala/scala/stargazers","contributors_url":"https://api.github.com/repos/scala/scala/contributors","subscribers_url":"https://api.github.com/repos/scala/scala/subscribers","subscription_url":"https://api.github.com/repos/scala/scala/subscription","commits_url":"https://api.github.com/repos/scala/scala/commits{/sha}","git_commits_url":"https://api.github.com/repos/scala/scala/git/commits{/sha}","comments_url":"https://api.github.com/repos/scala/scala/comments{/number}","issue_comment_url":"https://api.github.com/repos/scala/scala/issues/comments{/number}","contents_url":"https://api.github.com/repos/scala/scala/contents/{+path}","compare_url":"https://api.github.com/repos/scala/scala/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scala/scala/merges","archive_url":"https://api.github.com/repos/scala/scala/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scala/scala/downloads","issues_url":"https://api.github.com/repos/scala/scala/issues{/number}","pulls_url":"https://api.github.com/repos/scala/scala/pulls{/number}","milestones_url":"https://api.github.com/repos/scala/scala/milestones{/number}","notifications_url":"https://api.github.com/repos/scala/scala/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scala/scala/labels{/name}","releases_url":"https://api.github.com/repos/scala/scala/releases{/id}","created_at":"2011-12-01T05:02:34Z","updated_at":"2015-06-02T17:46:05Z","pushed_at":"2015-06-02T05:34:01Z","git_url":"git://github.com/scala/scala.git","ssh_url":"git@github.com:scala/scala.git","clone_url":"https://github.com/scala/scala.git","svn_url":"https://github.com/scala/scala","homepage":"http://www.scala-lang.org/","size":194211,"stargazers_count":4279,"watchers_count":4279,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":1100,"mirror_url":null,"open_issues_count":16,"forks":1100,"open_issues":16,"watchers":4279,"default_branch":"2.11.x"}},"_links":{"self":{"href":"https://api.github.com/repos/scala/scala/pulls/4534"},"html":{"href":"https://github.com/scala/scala/pull/4534"},"issue":{"href":"https://api.github.com/repos/scala/scala/issues/4534"},"comments":{"href":"https://api.github.com/repos/scala/scala/issues/4534/comments"},"review_comments":{"href":"https://api.github.com/repos/scala/scala/pulls/4534/comments"},"review_comment":{"href":"https://api.github.com/repos/scala/scala/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/scala/scala/pulls/4534/commits"},"statuses":{"href":"https://api.github.com/repos/scala/scala/statuses/9aae16aa231ad64e3987aaad2a206beaf10c76e0"}}}}