Use JavaScript's Array.sort.

dart/lib/compiler/implementation/lib/interceptors.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #library('dart:_interceptors');
 
 #import('dart:coreimpl');
 
 add$1(var receiver, var value) {
   if (isJsArray(receiver)) {
@@ skipping 344 matching lines @@
     return UNINTERCEPTED(receiver.every(f));
   } else {
     return Collections.every(receiver, f);
   }
 }
 
 // TODO(ngeoffray): Make it possible to have just one "sort" function ends
 // an optional parameter.
 
 sort$0(receiver) {
   if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort());

[floitsch, 2012/10/18 12:27:22]

After this if I would call sort$1(receiver, Comparable.compare).
It will reevaluate the isJsArray test, but make things much simpler.

[Lasse Reichstein Nielsen, 2012/10/18 13:04:00]

The trick is that this is simpler because we know the compare function - it will
not work on nulls. So instead of copying the array contents if it contains a
null, we just make it throw immediately.

[floitsch, 2012/10/18 13:46:51]

Since the shortcut only applies when it is going to throw, I wouldn't make the
special case.
If we really want to abort early I would rather special case in sort$1 (testing
if compare === Compare.compareTo).

   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, Comparable.compare);
+
+  int length = JS('int', '#.length', receiver);
+  if (length == 0 || length == 1) return;

[Lasse Reichstein Nielsen, 2012/10/18 13:04:00]

<= 1 should be fine, a JS Array's length can't be negative.

+  for (int i = 0; i < length; i++) {
+    // JavaScript's Array.prototype.sort has wierd semantics for null.
+    // It won't call compare and automatically pushes null/undefined
+    // to the end.
+    if (JS('var', '#[#]', receiver, i) == null) {
+      var other = JS('var', '#[#]', receiver, 0);
+      if (i == 0) {
+        other = JS('var', '#[#]', receiver, 1);
+      }
+      // Provoke a null error by comparing null to another element in
+      // the array.
+      Comparable.compare(null, other);
+    }
+  }
+
+  JS('void', '#.sort(#)', receiver, DART_CLOSURE_TO_JS(Comparable.compare));
 }
 
 sort$1(receiver, compare) {
   if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort(compare));
   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, compare);
+  int length = JS('int', '#.length', receiver);

[floitsch, 2012/10/18 12:27:22]

Just tell dart2js that receiver is a JavaScript-array, instead of having all
these JS here.

[ahe, 2012/11/23 08:43:42]

How do I do that?

[sra1, 2012/11/23 10:57:33]

This code is dominated by isJsArray(receiver).
Why is that not sufficient?

[floitsch, 2012/11/23 13:00:51]

It should be, and now with the new interceptor approach this should work even
better.

+  if (length == 0 || length == 1) return;
+  bool hasNull = false;
+  var array = receiver;
+  for (int i = 0; i < length; i++) {

[floitsch, 2012/10/18 12:27:22]

Given that you already run through the array, you could also see if every
element is a number (but not NaN, Infinity, -Infinity). If the compare function
=== Compare.compareTo (the common case) we could probably be even faster by
avoiding the expensive compareTo function and creating a three phase sorting:
- count the -0s and replace them with 0s.
- sort using function(x, y) { return x - y; }
- search for the first 0 and replace the first ones with as many -0s as there
were in the beginning.

[sra1, 2012/11/23 10:57:33]

This assumes compareTo returns num, not int.  I'm not convinced that is a wise
choice.

You would need to weed out values within 2x of the max magnitude since otherwise
the subtraction could overflow and return Infinity.

+    // JavaScript's Array.prototype.sort has wierd semantics for null.

[floitsch, 2012/10/18 12:27:22]

weird

+    // It won't call compare and automatically pushes null/undefined
+    // to the end.
+    if (JS('var', '#[#]', array, i) == null) {
+      if (!hasNull) {
+        array = JS('var', '#.slice(0)', array);

[floitsch, 2012/10/18 12:27:22]

Why do we need a copy? To avoid the try/finally?

[Lasse Reichstein Nielsen, 2012/10/19 07:03:21]

Because any NullSentinel in the original array would be visible during the call
to the compare function.

+      }
+      JS('var', '#[#] = #', array, i, const NullSentinel());
+      hasNull = true;
+    }
+  }
+  var jsCompare;
+  if (hasNull) {

[floitsch, 2012/10/18 12:27:22]

I would special case for the Compare.compare:
if (compare === Compare.compare && hasNull) jsCompare = ...;
In that case you don't even need to bind.

+    jsCompare = DART_CLOSURE_TO_JS(compareHelperNull);
+  } else {
+    jsCompare = DART_CLOSURE_TO_JS(compareHelper);
+  }
+  // [DART_CLOSURE_TO_JS] only accepts static or top-level functions.
+  // So we use [compareHelper] and JavaScript's
+  // Function.prototype.bind to create a new closure we can safely
+  // pass to JavaScript.
+  jsCompare = JS('var', '#.bind(#, #)', jsCompare, null, compare);

[Lasse Reichstein Nielsen, 2012/10/18 11:54:50]

Is 'bind' fast now? That would be great :)

Try replacing it with this and see which is faster:
JS("var",
   "(function(compare, jsCompare) { return function(a,b) { return
jsCompare(compare, a, b); }; })(#,#)",
    compare, jsCompare);

+
+  JS('void', '#.sort(#)', receiver, jsCompare);
+
+  if (hasNull) {
+    for (int i = 0; i < length; i++) {
+      var element = JS('var', '#[#]', array, i);
+      if (const NullSentinel() == element) {
+        element = null;
+      }
+      JS('var', '#[#] = #', receiver, i, element);
+    }
+  }
 }
 
 isNegative(receiver) {
   if (receiver is num) {
     return (receiver == 0) ? (1 / receiver) < 0 : receiver < 0;
   } else {
     return UNINTERCEPTED(receiver.isNegative());
   }
 }
 
@@ skipping 293 matching lines @@
   } else {
     return UNINTERCEPTED(receiver.runtimeType);
   }
 }
 
 // TODO(lrn): These getters should be generated automatically for all
 // intercepted methods.
 get$toString(receiver) => () => toString(receiver);
 
 get$hashCode(receiver) => () => hashCode(receiver);