Extrinsic sorting: A benchmark

Submitted by admin on 25 September 2022 - 10:10am

Sorting algorithms are generally old hat to most programmers. They've either analyzed them to death in class, already written many of them, or work in a language where one is provided and they don't need to think about it. Or all three.

For PHP developers, we have a suite of sorting tools available to us: sort(), usort(), ksort(), uasort(), and various other letter combinations. All use Quick Sort internally, which is generally the best performing single-threaded option. Most importantly, many of them let us provide a custom comparison function to use when determining which of two values is larger or smaller.

However, that doesn't mean the last word has been spoken. Most sorting algorithms are all about picking what to compare to minimize the number of comparisons, not doing the actual comparison. Additionally, we don't always want to sort data by itself. Quite often, we need to sort records by some extrinsic value, such as a priority or before/after flags.

What are the performance characteristics of those options? Since my PSR-14 Event Dispatcher implementation, Tukio, supports both priorty and before/after logic, I wanted to see which was faster, and just how fast. The results were quite interesting!

Continue reading this post on PeakD.