Hi internals, This was previously discussed in https://externals.io/message/108841, but I figured it would make sense to create an RFC for this change: https://wiki.php.net/rfc/stable_sorting
As before, the implementation approach is to stick with the existing qsort and use a fallback comparison criterion, which is cheap to implement internally. The obvious alternative is to use a stable base sort like Timsort. I gave this a quick try in https://github.com/php/php-src/pull/5559, and it does better in some cases (already sorted data) and worse in others (random data). I don't plan to pursue this direction personally. (It may also be interesting to use pdqsort as the unstable base, which should make the "already sorted" case faster.) Regards, Nikita
