Какие алгоритмы сортировки применяется в usort?

Question

Я хочу отсортировать файлы по времени изменения по возрастанию и по убыванию.

Согласно этому ответу Похоже, этого лучше всего добиться, определив функцию обратного вызова сортировки и используя usort / uasort.

Однако из-за характера моего приложения я, скорее всего, столкнусь с некоторыми наихудшими сценариями для некоторых алгоритмов сортировки (например, почти в обратном порядке входной последовательности).

Поскольку каждое сравнение использует два доступа к файловой системе, которые частично выполняются на сетевых дисках, количество сравнений является критическим и должно быть сведено к минимуму. Других видов итераций может быть больше.

Итак, какие алгоритмы сортировки используют функции сортировки массивов в PHP? Quicksort? Multisort? Есть ли способ настроить это?

Должен ли я, возможно, перемешать массив перед сортировкой?

Или мне нужно написать собственную реализацию?

Знаете ли вы несколько хороших библиотек, которые предоставляют функции сортировки с настраиваемыми алгоритмами?

Какой алгоритм или способы решения этой проблемы минимизации сравнений вы бы порекомендовали?

Answer 1

На php.net/sort Я нашел это:

Примечание: Как и большинство функций сортировки PHP, sort () использует реализацию »Quicksort.

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

Я сделал некоторые тесты и быстрая сортировка PHP не рандомизирована, так что перемешайте ваш входной массив !!

Answer 2

Я провел несколько поисков, используя PHP OpenGrok , и, основываясь только на взглядах на имена функций и код скимминга, похоже, что usort реализован с помощью быстрой сортировки.

Чтобы минимизировать вызовы файловой системы, сделайте их один раз для каждого элемента в вашем массиве и сохраните результаты в другом массиве. Используйте этот второй массив в функции сравнения вместо повторных вызовов.