Which sort algorithms does PHP's usort apply?

Question

I want to sort files by modification time ascending and descending.

According to this answer It looks like this can best be achieved defining a sort callback function and using usort/uasort.

However because of the nature of my application I am likely to run into some worst case scenarios for some sort algorithms (for example almost reverse-ordered input sequence).

Because every comparison uses two file system accesses which are partly on network drives, the number of comparisons is critical and must be minimized. Other sorts of iterations can be more.

So what sort algorithms do PHP's array sort functions utilise? Quicksort? Multisort? Is there any way I can configure this?

Should I perhaps shuffle the array before sorting?

Or do I need to write my own implementation?

Do you know some good libraries that provide sort functions with configurable algorithms?

What algorithm or ways to solve this problem of minimizing comparisons would you recommend?

Answer 1

At php.net/sort I found this:

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

I believe that it uses a randomized quicksort, so there is no need for shuffling the array.

I did some tests and PHP's quicksort is not randomized, so shuffle your input array!!

Answer 2

I did a few searches using PHP OpenGrok, and just based on some glancing at function names and skimming code, it looks like usort is implemented with quicksort.

To minimize the file system calls, make them once for each item in your array, and store the results in another array. Use that second array in your comparator function instead of making the calls again.