Re: [RFC] Make sorting stable

On Tue, May 12, 2020 at 4:18 PM Nikita Popov <nikita.ppv@gmail.com> wrote: > 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.) > If nothing new comes up, I plan to open voting on this RFC soon. Nikita