¿Implementación de Javascript Array.sort?
¿Qué algoritmo utiliza la función JavaScript Array#sort()? Entiendo que se pueden necesitar todo tipo de argumentos y funciones para realizar diferentes tipos de tipos, simplemente estoy interesado en qué algoritmo utiliza el tipo básico.
Acabo de echar un vistazo a la fuente de 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 de C++ std::qsortque implementa alguna variación de ordenación rápida (generalmente introclasificación ).
Las matrices contiguas de tipo no numérico se encadenan y ordenan usando mergesort, si está disponible (para obtener una clasificación estable) o qsortsi no hay ninguna ordenación por combinación disponible.
Para otros tipos (matrices no contiguas y presumiblemente para matrices asociativas), WebKit usa ordenación por selección (que ellos llaman ordenación "mínima" ) 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 del código para ver para qué tipos se utiliza qué método de clasificación.
Y luego hay joyas 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 “solucione” esto tenga una mejor comprensión del tiempo de ejecución asintótico que el autor 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).
Si observa este error 224128 , parece que Mozilla está utilizando MergeSort.
No existe ningún requisito preliminar para que JS utilice un algoritmo de clasificación específico. Como muchos han mencionado aquí, Mozilla usa ordenación por combinació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.
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;
}
}
};
Actualización A partir de 2018, V8 usa TimSort, gracias @celwell. Fuente
