Implementación Javascript Array.sort?

¿Qué algoritmo usa la Array#sort()función JavaScript ? Entiendo que puede tomar todo tipo de argumentos y funciones para realizar diferentes tipos de tipos, simplemente estoy interesado en qué algoritmo utiliza el tipo de vainilla.

Si observa este error 224128 , parece que Mogeilla está utilizando MergeSort.

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

Las matrices numéricas (o matrices de tipo primitivo) se ordenan utilizando la función de biblioteca estándar C ++ std::qsortque implementa alguna variación de clasificación rápida (generalmente introsort ).

Las matrices contiguas de tipo no numérico se clasifican en cadena y se clasifican utilizando mergesort, si está disponible (para obtener una clasificación estable) oqsort si no hay una clasificación de fusión disponible.

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

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 realmente "arregle" esto comprenda mejor el tiempo de ejecución asintótico que el autor de este comentario, y se dé cuenta de que la clasificación de radix 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).

No hay un requisito de borrador para que JS use un algoritmo 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 arreglos más pequeños.

Fuente del motor V8

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

Actualización A partir de 2018 V8 usa TimSort, gracias @celwell. Fuente

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

Después de un poco más de investigación, parece, para Mozilla / Firefox, que Array.sort () usa mergesort. Mira el código aquí .

Creo que eso dependerá de a qué implementación de navegador se refiera.

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

Sin embargo, IE es de código cerrado, por lo que es posible que deba consultar a alguien en Microsoft.

A partir de V8 v7.0 / Chrome 70, V8 utiliza TimSort , el algoritmo de clasificación de Python. Chrome 70 fue lanzado el 13 de septiembre de 2018.

Consulte la publicación en el blog de desarrollo de V8 para obtener detalles sobre este cambio. También puede leer el código fuente o el parche 1186801 .

La función Array.sort () de JavaScript tiene mecanismos internos para seleccionar el mejor algoritmo de ordenación (QuickSort, MergeSort, etc.) en función del tipo de datos de los elementos de la matriz.

intente esto con una ordenación rápida:

function sort(arr, compareFn = (a, b) => a <= b) {

    if (!arr instanceof Array || arr.length === 0) {
        return arr;
    }

    if (typeof compareFn !== 'function') {
        throw new Error('compareFn is not a function!');
    }

    const partition = (arr, low, high) => {
        const pivot = arr[low];
        while (low < high) {
            while (low < high && compareFn(pivot, arr[high])) {
                --high;
            }
            arr[low] = arr[high];
            while (low < high && compareFn(arr[low], pivot)) {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    };

    const quickSort = (arr, low, high) => {
        if (low < high) {
            let pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
        return arr;
    };

    return quickSort(arr, 0, arr.length - 1);
}