Matriz Javascript.¿ordenar la implementación?

Acabo de echar un vistazo a la WebKit (Chrome, Safari source) fuente. Dependiendo del tipo de matriz, se utilizan diferentes métodos de ordenación:

Los arrays numéricos (o arrays de tipo primitivo) se ordenan usando la función de biblioteca estándar de C++ std::qsort que implementa alguna variación de quicksort (usualmente introsort).

Los arrays contiguos de tipo no numérico se stringifican y ordenan usando mergesort, si está disponible (para obtener un stable ordenando) o qsort si no hay ordenación combinada disponible.

Para otros tipos (arrays no contiguos y presumiblemente para arrays asociativos) WebKit usa selection sort (que llaman "min" sort) o, en algunos casos, ordena a través de un árbol AVL. Desafortunadamente, la documentación aquí es bastante vaga, por lo que tendría que rastrear las rutas de código para ver realmente para qué tipos se utiliza qué método de ordenación.

Y luego hay gemas como esta comentario:

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

– Esperemos que quien realmente "arregle" esto tenga una mejor comprensión del tiempo de ejecución asintótico que el escritor de este comentario, y se dé cuenta de que radix sort tiene una descripción de tiempo de ejecución un poco más compleja que simplemente O(N).

(Gracias a phsource por señalar el error en la respuesta original.)

El estándar ECMAScript no especifica qué algoritmo de ordenación se va a utilizar. De hecho, diferentes navegadores cuentan con diferentes algoritmos de clasificación. Por ejemplo, sort () de Mozilla/Firefox no es estable (en el sentido de ordenación de la palabra) al ordenar un mapa. Sort() de IE es estable.

No hay ningún requisito de borrador para que JS use un algoritmo de ordenación específico. Como muchos han mencionado aquí, Mozilla usa merge sort.Sin embargo, en el código fuente v8 de Chrome, a partir de hoy, utiliza QuickSort e InsertionSort, para matrices más pequeñas.

Fuente del motor V8

De las Líneas 807-891

  var QuickSort = function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
      var v2 = a[third_index];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
      a[third_index] = a[low_end];
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
        }
      }
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  };

Después de un poco más de investigación, aparece, para Mozilla/Firefox, esa matriz.sort () usa mergesort. Ver el código aquí.

Creo que eso dependería de la implementación del navegador a la que se refiera.

Cada tipo de navegador tiene su propia implementación de motor javascript, por lo que depende. Puede comprobar los repositorios de código fuente para Mozilla y Webkit / Khtml para diferentes implementaciones.

IE es de código cerrado sin embargo, por lo que puede que tenga que preguntar a alguien en Microsoft.