a.patch

diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java
index df22af7..112da78 100644
--- a/core/src/main/java/org/jruby/RubyArray.java
+++ b/core/src/main/java/org/jruby/RubyArray.java
@@ -4209,9 +4209,11 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
                 }
             }
         } else {
+            Object typeId = getTypeIdForCMP();
+
             for (i = 0; i < realLength; i++) {
                 v = eltOk(i);
-                if (result == UNDEF || optimizedCmp(context, v, result/*, cmp_opt*/) > 0) {
+                if (result == UNDEF || optimizedCmp(context, v, result/*, cmp_opt*/, typeId) > 0) {
                     result = v;
                 }
             }
@@ -4246,9 +4248,11 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
             }
         }
         else {
+            Object typeId = getTypeIdForCMP();
+
             for (i = 0; i < realLength; i++) {
                 v = eltOk(i);
-                if (result == UNDEF || optimizedCmp(context, v, result/*, cmp_opt*/) < 0) {
+                if (result == UNDEF || optimizedCmp(context, v, result/*, cmp_opt*/, typeId) < 0) {
                     result = v;
                 }
             }
@@ -4257,6 +4261,14 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return result;
     }
 
+    private Object getTypeIdForCMP() {
+        if (realLength <= 0) return null;
+
+        RubyModule meta = eltOk(0).getMetaClass();
+
+        return meta.isBuiltin(OP_CMP.realName()) ? meta.getInvalidator() : null;
+    }
+
     @JRubyMethod(name = "min")
     public IRubyObject min(ThreadContext context, IRubyObject num, Block block) {
         if (!num.isNil()) {
@@ -4266,13 +4278,13 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return min(context, block);
     }
 
-    private static final int optimizedCmp(ThreadContext context, IRubyObject a, IRubyObject b/*, IRubyObject data*/) {
+    private static final int optimizedCmp(ThreadContext context, IRubyObject a, IRubyObject b/*, IRubyObject data*/, Object typeId) {
         // TODO: check for overwritten <=> on Fixnum and String
-        if (a instanceof RubyFixnum && b instanceof RubyFixnum /*&& CMP_OPTIMIZABLE(data, Fixnum)*/) {
+        if (a instanceof RubyFixnum && b instanceof RubyFixnum && typeId == context.runtime.getFixnum().getInvalidator().getData() /*&& CMP_OPTIMIZABLE(data, Fixnum)*/) {
             long aLong = ((RubyFixnum)a).getLongValue();
             long bLong = ((RubyFixnum)b).getLongValue();
             return aLong > bLong ? 1 : aLong < bLong ? -1 : 0;
-        } else if (a instanceof RubyString && b instanceof RubyString /*&& CMP_OPTIMIZABLE(data, String)*/) {
+        } else if (a instanceof RubyString && b instanceof RubyString && typeId == context.runtime.getFixnum().getInvalidator().getData()  /*&& CMP_OPTIMIZABLE(data, String)*/) {
             return ((RubyString)a).op_cmp((RubyString)b);
         }
 

after.txt

jruby ../snippets/ben.rb
Warming up --------------------------------------
                   2    85.404k i/100ms
                  10    89.492k i/100ms
                  50    53.209k i/100ms
                 250    18.410k i/100ms
Calculating -------------------------------------
                   2      5.750M (±10.6%) i/s -     28.354M
                  10      3.235M (± 7.5%) i/s -     16.109M
                  50      1.011M (± 5.2%) i/s -      5.055M
                 250    224.001k (± 5.3%) i/s -      1.123M

before.txt

Warming up --------------------------------------
               debug    77.501k i/100ms
Calculating -------------------------------------
               debug      2.687M (± 8.3%) i/s -     13.330M
system ~/work/jruby master 509% jruby ../snippets/ben.rb
Warming up --------------------------------------
                   2    95.460k i/100ms
                  10   102.590k i/100ms
                  50    90.070k i/100ms
                 250    56.599k i/100ms
Calculating -------------------------------------
                   2     11.607M (±14.3%) i/s -     56.226M
                  10      9.241M (±10.7%) i/s -     45.550M
                  50      4.320M (± 8.8%) i/s -     21.437M
                 250      1.307M (± 6.7%) i/s -      6.509M