Javascript-Array.Art der Umsetzung?

Wenn man sich diese Fehler Zwei hundert vier und zwanzig tausend eins hundert acht und zwanzig, es scheint, dass MergeSort verwendet wird, die von Mozilla.

InformationsquelleAutor Britton

Gibt es keinen Entwurf Voraussetzung für JS eine bestimmte Sortierung algorthim. Wie viele hier erwähnt haben, die von Mozilla verwendete merge-sort.Allerdings In Chrome-v8-source-code, wie von heute, es nutzt QuickSort und InsertionSort, für kleinere arrays.

V8-Motor Quelle

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 V8 verwendet TimSort, danke @celwell. Quelle

InformationsquelleAutor Joe Thomas

Nachdem einige weitere Forschung, es scheint, für Mozilla/Firefox, dass Array.sort() verwendet mergesort. Finden Sie unter den code hier.

InformationsquelleAutor latortuga

Als der V8 v7.0 /Chrom 70, V8 verwendet TimSort, Python-Sortier-Algorithmus. Chrome 70 wurde veröffentlicht am September 13, 2018.

Sehen die der post auf den V8-dev blog für details über diese änderung. Sie können auch Lesen Sie die source code oder patch 1186801.

InformationsquelleAutor Boris