JavaScript реализация Array.sort?

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

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

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

Для других типов (массивы, состоящие из нескольких несмежных участков, и по-видимому для ассоциативных массивов) WebKit использует любой вид выбора (который они называют вид “min” ), или, в некоторых случаях, это сортирует через дерево AVL. К сожалению, документация здесь довольно неопределенна, таким образом, you’d должны проследить пути выполнения кода для фактического видения, какие типы, какой метод сортировки используется.

И затем существуют драгоценные камни как [1 110] этот комментарий :

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

†“Let’s просто надеются, что, кто бы ни на самом деле “fixes” это имеет лучшее понимание асимптотического времени выполнения, чем писатель этого комментария, и понимает, что вид основания имеет немного более сложное описание во время выполнения, чем просто O (N).

(Благодаря phsource для указания на ошибку в исходном ответе.)

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

Еще после некоторого исследования кажется для Mozilla/Firefox, что Array.sort () использует сортировку с объединением. Посмотрите код здесь .

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

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

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

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