Use JavaScript's Array.sort.

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

Index: dart/lib/compiler/implementation/lib/interceptors.dart
diff --git a/dart/lib/compiler/implementation/lib/interceptors.dart b/dart/lib/compiler/implementation/lib/interceptors.dart
index 680af43e4408e4c86110e683b17e77d774d02123..d958422d3774bf7f2d2b016c1d7ed4ed1e80f5fd 100644
--- a/dart/lib/compiler/implementation/lib/interceptors.dart
+++ b/dart/lib/compiler/implementation/lib/interceptors.dart
@@ -364,13 +364,16 @@ every(receiver, f) {
 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) {