Make sort method generic. This eliminates a large number of dynamic calls that slow down sorting un…

sdk/lib/internal/sort.dart

 // Copyright (c) 2011, 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.
 
 part of dart._internal;
 
 /**
  * Dual-Pivot Quicksort algorithm.
  *
  * This class implements the dual-pivot quicksort algorithm as presented in
@@ skipping 11 matching lines @@
    * [:compare:] function.
    *
    * The [:compare:] function takes two arguments [:x:] and [:y:] and returns
    *  -1 if [:x < y:],
    *   0 if [:x == y:], and
    *   1 if [:x > y:].
    *
    * The function's behavior must be consistent. It must not return different
    * results for the same values.
    */
-  static void sort(List a, int compare(a, b)) {
+  static void sort/*<E>*/(List/*<E>*/ a, int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
     _doSort(a, 0, a.length - 1, compare);
   }
 
   /**
    * Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive)
    * of the given list [:a:].
    *
    * If the given range is invalid an "OutOfRange" error is raised.
    * TODO(floitsch): do we want an error?
    *
    * See [:sort:] for requirements of the [:compare:] function.
    */
-  static void sortRange(List a, int from, int to, int compare(a, b)) {
+  static void sortRange/*<E>*/(List/*<E>*/ a, int from, int to, int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
     if ((from < 0) || (to > a.length) || (to < from)) {
       throw "OutOfRange";
     }
     _doSort(a, from, to - 1, compare);
   }
 
   /**
    * Sorts the list in the interval [:left:] to [:right:] (both inclusive).
    */
-  static void _doSort(List a, int left, int right, int compare(a, b)) {
+  static void _doSort/*<E>*/(List/*<E>*/ a, int left, int right, int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
     if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
       _insertionSort(a, left, right, compare);
     } else {
       _dualPivotQuicksort(a, left, right, compare);
     }
   }
 
-  static void _insertionSort(List a, int left, int right, int compare(a, b)) {
+  static void _insertionSort/*<E>*/(List/*<E>*/ a, int left, int right, int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
     for (int i = left + 1; i <= right; i++) {
       var el = a[i];
       int j = i;
       while ((j > left) && (compare(a[j - 1], el) > 0)) {
         a[j] = a[j - 1];
         j--;
       }
       a[j] = el;
     }
   }
 
-  static void _dualPivotQuicksort(List a,
+  static void _dualPivotQuicksort/*<E>*/(List/*<E>*/ a,
                                   int left, int right,
-                                  int compare(a, b)) {
+                                  int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
     assert(right - left > _INSERTION_SORT_THRESHOLD);
 
     // Compute the two pivots by looking at 5 elements.
     int sixth = (right - left + 1) ~/ 6;
     int index1 = left + sixth;
     int index5 = right - sixth;
     int index3 = (left + right) ~/ 2;  // The midpoint.
     int index2 = index3 - sixth;
     int index4 = index3 + sixth;
 
@@ skipping 247 matching lines @@
     } else {
       // The second partition looks as follows:
       // [  *  |  >= pivot1 && <= pivot2  | * ]
       //        ^                        ^
       //       less                    great
       // Simply sort it by recursive descent.
       _doSort(a, less, great, compare);
     }
   }
 }