Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:110143
MIME-Version: 1.0
Date: Tue, 12 May 2020 16:18:47 +0200
Message-ID: <CAF+90c9zVKL2au+LnkQk2w8VmKxh1Aw_Uvz9xF7f-PZF7ziXvA@mail.gmail.com>
To: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="00000000000044fe1205a57425a2"
Subject: [RFC] Make sorting stable
From: nikita.ppv@gmail.com (Nikita Popov)

--00000000000044fe1205a57425a2
Content-Type: text/plain; charset="UTF-8"

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

--00000000000044fe1205a57425a2--