Javascript Array.sort Implementierung?

Welchen Algorithmus verwendet die JavaScript- Array#sort()Funktion? Ich verstehe, dass es allerlei Argumente und Funktionen erfordern kann, um verschiedene Arten von Sortierungen durchzuführen. Ich bin einfach daran interessiert, welchen Algorithmus die Vanille-Sortierung verwendet.

Wenn Sie sich diesen Fehler 224128 ansehen , scheint MergeSort von Mozilla verwendet zu werden.

Ich habe mir gerade die WebKit- Quelle (Chrome, Safari…) angesehen . Abhängig von der Art des Arrays werden verschiedene Sortiermethoden verwendet:

Numerische Arrays (oder Arrays vom primitiven Typ) werden mithilfe der C ++ - Standardbibliotheksfunktion sortiert, die std::qsorteinige Variationen von Quicksort (normalerweise Introsort ) implementiert .

Zusammenhängende Arrays vom nicht numerischen Typ werden mithilfe von Mergesort stringiert und sortiert, sofern verfügbar (um eine stabile Sortierung zu erhalten) oder qsortwenn keine Zusammenführungssortierung verfügbar ist.

Für andere Typen (nicht zusammenhängende Arrays und vermutlich für assoziative Arrays) verwendet WebKit entweder eine Auswahlsortierung (die sie als "min" -Sortierung bezeichnen ) oder in einigen Fällen eine Sortierung über einen AVL-Baum. Leider ist die Dokumentation hier ziemlich vage, sodass Sie die Codepfade nachverfolgen müssen, um tatsächlich zu sehen, für welche Typen welche Sortiermethode verwendet wird.

Und dann gibt es Edelsteine ​​wie diesen Kommentar :

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

- Hoffen wir nur, dass jeder, der dies tatsächlich „behebt“, die asymptotische Laufzeit besser versteht als der Verfasser dieses Kommentars und erkennt, dass die Radix-Sortierung eine etwas komplexere Laufzeitbeschreibung hat als einfach O (N).

(Vielen Dank an phsource für den Hinweis auf den Fehler in der ursprünglichen Antwort.)

Es gibt keine Entwurfsanforderung für JS, ein bestimmtes Sortieralgorthim zu verwenden. Wie viele hier erwähnt haben, verwendet Mozilla die Zusammenführungssortierung. Im Chrome v8-Quellcode werden jedoch ab heute QuickSort und InsertionSort für kleinere Arrays verwendet.

V8 Motorquelle

Von den Linien 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;
      }
    }
  };

Update Ab 2018 verwendet V8 TimSort, danke @celwell. Quelle

Der ECMAscript-Standard legt nicht fest, welcher Sortieralgorithmus verwendet werden soll. In der Tat bieten verschiedene Browser unterschiedliche Sortieralgorithmen. Zum Beispiel ist Mozilla / Firefoxs sort ( ) beim Sortieren einer Karte nicht stabil (im Sinne des Wortes). IE sort () ist stabil.

Nach einigen weiteren Untersuchungen scheint es, dass Array.sort () für Mozilla / Firefox Mergesort verwendet. Siehe den Code hier .

Ich denke, das hängt davon ab, auf welche Browser-Implementierung Sie sich beziehen.

Jeder Browsertyp hat eine eigene Implementierung der Javascript-Engine, es kommt also darauf an. Sie können die Quellcode-Repos für Mozilla und Webkit / Khtml auf verschiedene Implementierungen überprüfen.

IE ist jedoch eine geschlossene Quelle, sodass Sie möglicherweise jemanden bei Microsoft fragen müssen.

Ab V8 v7.0 / Chrome 70 verwendet V8 TimSort , den Sortieralgorithmus von Python. Chrome 70 wurde am 13. September 2018 veröffentlicht.

Weitere Informationen zu dieser Änderung finden Sie im Beitrag im V8-Entwicklerblog . Sie können auch den Quellcode oder den Patch 1186801 lesen .

Die Array.sort () -Funktion von JavaScript verfügt über interne Mechanismen zur Auswahl des besten Sortieralgorithmus (QuickSort, MergeSort usw.) auf der Grundlage des Datentyps der Array-Elemente.

versuchen Sie dies mit schneller Sortierung:

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