Implementação Javascript Array.sort?

Qual algoritmo usa a function JavaScript Array#sort() ? Eu entendo que pode levar todo tipo de argumentos e funções para executar tipos diferentes de tipos, estou simplesmente interessado em qual algoritmo o tipo baunilha usa.

Se você olhar para este bug 224128 , parece que o MergeSort está sendo usado pelo Mozilla.

Acabei de dar uma olhada na fonte WebKit (Chrome, Safari …). Dependendo do tipo de matriz, são usados ​​methods de sorting diferentes:

Matrizes numéricas (ou matrizes de tipo primitivo) são ordenadas usando a function de biblioteca padrão C ++ std::qsort que implementa alguma variação de quicksort (geralmente introsort ).

Matrizes contíguas de tipo não numérico são estendidas e ordenadas usando o mergesort, se disponível (para obter uma sorting estável) ou qsort se nenhuma ordenação de mesclagem estiver disponível.

Para outros tipos (matrizes não contíguas e presumivelmente para matrizes associativas), o WebKit usa a sorting de seleção (que eles chamam de sorting “min” ) ou, em alguns casos, classifica através de uma tree AVL. Infelizmente, a documentação aqui é bastante vaga, então você teria que rastrear os caminhos de código para ver de que tipos o método de sorting é usado.

E depois há jóias como este comentário :

 // 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). 

– Vamos apenas esperar que quem realmente “conserte” isso tenha um melhor entendimento do tempo de execução assintótico do que o escritor deste comentário, e perceba que radix sort tem uma descrição de tempo de execução um pouco mais complexa que simplesmente O (N).

(Obrigado ao phsource por apontar o erro na resposta original.)

O padrão ECMAscript não especifica qual algoritmo de sorting deve ser usado. De fato, diferentes navegadores apresentam diferentes algoritmos de sorting. Por exemplo, o sort () do Mozilla / Firefox não é estável (no sentido de ordenação da palavra) ao ordenar um mapa. A sorting do IE () é estável.

Não há requisito de rascunho para o JS usar um algoritmo de ordenação específico. Como muitos mencionaram aqui, o Mozilla usa o merge sort.No entanto, no código-fonte da versão 8 do Chrome, a partir de hoje, ele usa QuickSort e InsertionSort, para matrizes menores.

V8 Engine Source

Das linhas 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; } } }; 

Depois de mais algumas pesquisas, parece que, para o Mozilla / Firefox, o Array.sort () usa o mesclar o fusível. Veja o código aqui .

Eu acho que isso dependeria de qual implementação do navegador você está se referindo.

Cada tipo de navegador tem sua própria implementação de mecanismo de javascript, portanto, isso depende. Você pode verificar os repositorys de código fonte para Mozilla e Webkit / Khtml para diferentes implementações.

IE é fechado, no entanto, você pode ter que perguntar a alguém na microsoft.