¿Implementación de Javascript Array.sort?

merge sort javascript

Question

¿Qué algoritmo usa la función Array#sort() JavaScript? Entiendo que puede tomar todo tipo de argumentos y funciones para realizar diferentes tipos de géneros, simplemente me interesa saber qué algoritmo usa el género vanilla.

Answer 1

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

Las matrices numéricas (o las matrices de tipo primitivo) se ordenan utilizando la función de biblioteca estándar de C ++, std::qsort que implementa alguna variación de quicksort (generalmente introsort ).

Las matrices contiguas de tipo no numérico se codifican y ordenan utilizando mergesort, si está disponible (para obtener una clasificación estable) o qsort si no está disponible la clasificación por fusión.

Para otros tipos (matrices no contiguas y, presumiblemente, para matrices asociativas), WebKit utiliza la ordenación de selección (que denominan ordenación "mínima" ) o, en algunos casos, ordena a través de un árbol AVL. Lamentablemente, la documentación aquí es bastante vaga, por lo que tendrías que rastrear las rutas del código para ver realmente para qué tipos se utiliza el método de clasificación.

Y luego hay gemas como este 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 sea que realmente "solucione" esto comprenda mejor el tiempo de ejecución asintótico que el autor de este comentario, y se da cuenta de que el tipo de raíz tiene una descripción del 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).

Answer 2

Creo que eso dependerá de la implementación del navegador al que se refiera.

Cada tipo de navegador tiene su propia implementación de motor de JavaScript, por lo que depende. Puede consultar 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 es posible que tengas que preguntarle a alguien en microsoft.

Answer 3

Después de algunas investigaciones más, parece que, para Mozilla / Firefox, Array.sort () usa mergesort. Vea el código here .

Answer 4

El estándar ECMAscript no especifica qué algoritmo de clasificación se va a utilizar. De hecho, diferentes navegadores presentan diferentes algoritmos de ordenamiento. Por ejemplo, la clasificación de Mozilla / Firefox () no es stable (en el sentido de clasificación de la palabra) al ordenar un mapa. El tipo de IE () es estable.

Answer 5

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

https://github.com/v8/v8/blob/master/src/js/array.js

Desde las líneas 807 a 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;
      }
    }
  };

Answer 6

Si nos fijamos en este error 224128 , parece que Mozilla está utilizando MergeSort.