Реализация Javascript Array.sort?

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

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

Однако IE является закрытым исходным кодом, поэтому вам, возможно, придется спросить кого-нибудь в Microsoft.

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

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

Если вы посмотрите на эту ошибку 224128, окажется, что MergeSort используется Mozilla.

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

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

Смежные массивы нечислового типа преобразуются в строки и сортируются с использованием сортировки слиянием, если она доступна (для получения стабильной сортировки), или 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 за указание на ошибку в исходном ответе.)

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

Источник двигателя V8

По линиям 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;
      }
    }
  };

Обновлять Начиная с 2018 года V8 использует TimSort, спасибо @celwell. Источник

Начиная с V8 v7.0 / Chrome 70, V8 использует TimSort, алгоритм сортировки Python. Chrome 70 был выпущен 13 сентября 2018 года.

Подробнее об этом изменении см. сообщение в блоге разработчиков V8. Вы также можете прочитать исходный код или патч 1186801.

Функция JavaScript Array.sort () имеет внутренние механизмы для выбора лучшего алгоритма сортировки (QuickSort, MergeSort и т. д.) На основе типа данных элементов массива.

попробуйте это с быстрой сортировкой:

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