reverted refactoring for efficiency

1 files changed, 206 insertions, 23 deletions

diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala
index 61a29ea767..9766a1aa77 100644
--- a/src/library/scala/util/Sorting.scala
+++ b/src/library/scala/util/Sorting.scala
@@ -6,7 +6,7 @@
 **                          |/                                          **
 \*                                                                      */
 
-// $Id: $
+// $Id$
 
 
 package scala.util
@@ -190,7 +190,7 @@ object Sorting {
     sort2(off, len)
   }
 
-  private def sort1[T <: AnyVal](x: Array[T], off: Int, len: Int, compare: (T, T) => Int) {
+  private def sort1(x: Array[Int], off: Int, len: Int) {
     def swap(a: Int, b: Int) {
       val t = x(a)
       x(a) = x(b)
@@ -208,13 +208,10 @@ object Sorting {
       }
     }
     def med3(a: Int, b: Int, c: Int) = {
-      val ab = compare(x(a), x(b))
-      val bc = compare(x(b), x(c))
-      val ac = compare(x(a), x(c))
-      if (ab < 0) {
-        if (bc < 0) b else if (ac < 0) c else a
+      if (x(a) < x(b)) {
+        if (x(b) < x(c)) b else if (x(a) < x(c)) c else a
       } else {
-        if (bc > 0) b else if (ac > 0) c else a
+        if (x(b) > x(c)) b else if (x(a) > x(c)) c else a
       }
     }
     def sort2(off: Int, len: Int) {
@@ -223,7 +220,7 @@ object Sorting {
         var i = off
         while (i < len + off) {
           var j = i
-          while (j>off && compare(x(j-1), x(j)) > 0) {
+          while (j>off && x(j-1) > x(j)) {
             swap(j, j-1)
             j -= 1
           }
@@ -252,23 +249,19 @@ object Sorting {
         var d = c
         var done = false
         while (!done) {
-          var xv = compare(x(b), v)
-          while (b <= c && xv <= 0) {
-            if (xv == 0) {
+          while (b <= c && x(b) <= v) {
+            if (x(b) == v) {
               swap(a, b)
               a += 1
             }
             b += 1
-            if (b <= c) xv = compare(x(b), v)
           }
-          xv = compare(x(c), v)
-          while (c >= b && xv >= 0) {
-            if (xv == 0) {
+          while (c >= b && x(c) >= v) {
+            if (x(c) == v) {
               swap(c, d)
               d -= 1
             }
             c -= 1
-            if (c >= b) xv = compare(x(c), v)
           }
           if (b > c) {
             done = true
@@ -298,16 +291,206 @@ object Sorting {
     sort2(off, len)
   }
 
-  private def sort1(x: Array[Int], off: Int, len: Int) {
-    sort1(x, off, len, (x: Int, y: Int) => x compare y)
-  }
-
   private def sort1(x: Array[Double], off: Int, len: Int) {
-    sort1(x, off, len, (x: Double, y: Double) => x compare y)
+    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
+          }
+          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
+            var 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
+          }
+        }
+
+        // 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)
   }
 
   private def sort1(x: Array[Float], off: Int, len: Int) {
-    sort1(x, off, len, (x: Float, y: Float) => x compare y)
+    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
+          }
+          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
+            var 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
+          }
+        }
+
+        // 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)
   }
 
   private def stableSort[K](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) {