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 346 matching lines @@
     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());
   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, Comparable.compare);
+  JS('var', '#.sort(#)', receiver, DART_CLOSURE_TO_JS(Comparable.compare));

[kasperl, 2012/10/18 07:46:36]

'var' -> 'void'?

[ahe, 2012/10/18 10:37:36]

Done.

 }
 
 sort$1(receiver, compare) {
   if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort(compare));
   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, compare);
+  var jsCompare = JS('var', '(function (compareHelper, compare) {'

[sra1, 2012/10/18 07:44:39]

A few linebreaks might improve the indentation, e.g.

jsCompare =
    JS('var',
       '(funct....

[ahe, 2012/10/18 10:37:36]

Using bind instead.

+                     ' return function (a, b) { return compareHelper(compare, a, b); } })(#, #)',

[sra1, 2012/10/18 07:44:39]

sort
calls function (a, b), which
calls the function returned by DART_CLOSURE_TO_JS, which
  pulls in the isolate library    # unnecessary in this context
  calls some isolate code         # unnecessary in this context
calls compareHelper.call$3 which  # probably could be eliminated
calls compare.call$2(a, b)

Without some more work here, this could be noticeably slower than the equivalent
JavaScript program.

[kasperl, 2012/10/18 07:46:36]

Fix long line with a bit more adjacent string concat?

[ahe, 2012/10/18 10:37:36]

You are correct.

I have used tests/co19/src/LibTest/core/List/sort_A01_t06.dart to benchmark
this.

Original DualPivotQuickSort is pretty fast: 228ms

This is what I'm using now:

  jsCompare = DART_CLOSURE_TO_JS(compareHelper);
  jsCompare = JS('var', '#.bind(#, #)', jsCompare, null, compare);

More than twice as slow: 550ms

It improves if I cheat (in a fairly general way):

  jsCompare = JS('var', r'#.call$2.bind(#)', compare, compare);

to: 467ms

But if I cheat even further and does:

  jsCompare = JS('var', r'#.call$2', compare);

It becomes really fast: 164ms (which is significantly better than 228ms).

In those numbers I also included a fix for what Lasse pointed out. This means
that I have to run through the array to see if it has nulls. If I remove that
check, the test runs in about the same time.

Kasper and I concluded that we need a smarter way to extract a JS closure from a
Dart closure, but that we should land this change.

[ahe, 2012/10/18 10:37:36]

Using bind which is shorter.

+                     DART_CLOSURE_TO_JS(compareHelper), compare);
+  JS('var', '#.sort(#)', receiver, jsCompare);

[kasperl, 2012/10/18 07:46:36]

'var' -> 'void'?

[Lasse Reichstein Nielsen, 2012/10/18 08:23:28]

JavaScript's sort is hard-coded to sort null/undefined after all
non-null/undefined elements, *without calling the compare function*. That might
not be compatible with the compare function if one is provided. It's also
slightly iffy that it doesn't throw on "[null,null,1].sort()" when null doesn't
implement compareTo and 1.compareTo(null) throws.

[ahe, 2012/10/18 10:37:36]

Done.

[ahe, 2012/10/18 10:37:36]

Done.

 }
 
 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);