Implementação Javascript Array.sort?

Qual algoritmo usa a Array#sort()função JavaScript ? Entendo que podem ser necessários todos os tipos de argumentos e funções para realizar diferentes tipos de tipos; estou simplesmente interessado em qual algoritmo a classificação de baunilha usa.

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

Acabei de dar uma olhada na fonte do WebKit (Chrome, Safari ...) . Dependendo do tipo de matriz, diferentes métodos de classificação são usados:

Matrizes numéricas (ou matrizes do tipo primitivo) são classificadas usando a função de biblioteca padrão C ++, std::qsortque implementa alguma variação do quicksort (geralmente introsort ).

Matrizes contíguas do tipo não numérico são estritas e classificadas usando mergesort, se disponível (para obter uma classificação estável) ou qsortse nenhuma classificação de mesclagem estiver disponível.

Para outros tipos (matrizes não contíguas e presumivelmente para matrizes associativas), o WebKit usa a classificação por seleção (que eles chamam de classificação “min” ) ou, em alguns casos, classifica por meio de uma árvore AVL. Infelizmente, a documentação aqui é bastante vaga, portanto você teria que rastrear os caminhos de código para realmente ver quais tipos de métodos de classificação são usados.

E então existem gemas 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 torcer para que quem "corrige" isso tenha uma melhor compreensão do tempo de execução assintótico do que o autor deste comentário, e perceba que a classificação radix possui uma descrição do tempo de execução um pouco mais complexa do que simplesmente O (N).

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

Não há um requisito preliminar para o JS usar um algorthim de classificação específico. Como muitos mencionaram aqui, o Mozilla usa classificação por mesclagem. No entanto, no código-fonte v8 do Chrome, a partir de hoje, ele usa o QuickSort e o InsertionSort, para matrizes menores.

Fonte do mecanismo V8

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

Atualizar A partir de 2018, o V8 usa o TimSort, obrigado @celwell. Fonte

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

Após mais algumas pesquisas, parece que, para o Mozilla / Firefox, o Array.sort () usa o mergesort. Veja o código aqui .

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

Todo tipo de navegador possui sua própria implementação de mecanismo javascript, portanto depende. Você pode verificar os repositórios de código-fonte do Mozilla e Webkit / Khtml para diferentes implementações.

No entanto, o IE é de código fechado, portanto, talvez você precise perguntar a alguém na microsoft.

A partir da V8 v7.0 / Chrome 70, a V8 usa o TimSort , o algoritmo de classificação do Python. O Chrome 70 foi lançado em 13 de setembro de 2018.

Veja a postagem no blog de desenvolvimento da V8 para obter detalhes sobre essa alteração. Você também pode ler o código-fonte ou o patch 1186801 .

A função Array.sort () do JavaScript possui mecanismos internos para selecionar o melhor algoritmo de classificação (QuickSort, MergeSort, etc.) com base no tipo de dados dos elementos da matriz.

tente isso com uma classificação 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);
}