массивы JavaScript.сортировать реализацию?

Я только что посмотрел на WebKit (Chrome, Safari ...)источник. В зависимости от типа массива используются различные методы сортировки:

числовые массивы (или массивы примитивного типа) сортируются с помощью функции стандартной библиотеки C++std::qsort который реализует некоторые вариации quicksort (обычно introsort).

непрерывные массивы нечислового типа строковые и сортируются с помощью mergesort, если доступно (для получения стабильной сортировки) или qsort Если сортировка слиянием недоступна.

для других типов (несмежных массивов и предположительно для ассоциативных массивов) WebKit использует либо сортировка выбор (которые они называют "мин" вроде) или, в некоторых случаях, он сортирует через дерево AVL. К сожалению, документация здесь довольно расплывчата, поэтому вам придется отслеживать пути кода, чтобы фактически увидеть, для каких типов какой метод сортировки используемый.

а еще есть драгоценные камни, как комментарий:

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

– давайте просто надеяться, что тот, кто на самом деле" исправляет " это, лучше понимает асимптотическое время выполнения, чем автор этого комментария, и понимает, что radix sort имеет несколько более сложное описание времени выполнения чем просто O (N).

(спасибо phsource за указание на ошибку в исходном ответе.)

стандарт ECMAscript не определяет, какой алгоритм сортировки должен использоваться. Действительно, разные браузеры имеют разные алгоритмы сортировки. Например, сортировка Mozilla / Firefox () не стабильный (в сортировочном смысле этого слова) при сортировке карты. Т. е. вроде() является стабильным.

для JS не требуется использовать определенный алгоритм сортировки. Как многие уже упоминали здесь, Mozilla использует сортировку слиянием.Однако в исходном коде Chrome v8 на сегодняшний день он использует QuickSort и InsertionSort для небольших массивов.

Двигатель V8 Движок Source

Из Строки 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;
      }
    }
  };

после некоторых дополнительных исследований, оказывается, для Mozilla / Firefox, что массив.сортировать() используется сортировка слиянием. Смотрите код здесь.

Я думаю, что это будет зависеть от того, на какую реализацию браузера вы ссылаетесь.

каждый тип браузера имеет свою собственную реализацию javascript engine, так что это зависит. Вы можете проверить репозитории исходного кода для Mozilla и Webkit/Khtml для разных реализаций.

IE является закрытым исходным кодом, однако, так что вам, возможно, придется спросить кого-то в microsoft.