Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:108841
MIME-Version: 1.0
Date: Wed, 4 Mar 2020 17:42:07 +0100
Message-ID: <CAF+90c9EAHbYQ+2iUA9vw13wMUevjXRMajYE9TLCoqf2YXCfBw@mail.gmail.com>
To: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="000000000000cf953905a00a1a16"
Subject: Make sorting stable
From: nikita.ppv@gmail.com (Nikita Popov)

--000000000000cf953905a00a1a16
Content-Type: text/plain; charset="UTF-8"

Hi internals,

Sorting function in PHP currently do not guarantee stability, which means
that the result order of elements that compare equal is not defined.

To achieve a stable sort, you need to do something like this (untested):

$arrayAndPos = [];
$pos = 0;
foreach ($array as $value) {
    $arrayAndPos[] = [$value, $pos++];
}
usort($arrayAndPos, function($a, $b) use($compare) {
    return $compare($a[0], $b[0]) ?: $a[1] <=> $b[1];
});
$array = [];
foreach ($arrayAndPos as $elem) {
    $array[] = $elem[0];
}

This is both cumbersome and very inefficient. Those temporary arrays
significantly increase memory usage, and hurt performance of the sort.

I believe that it is important for us to provide a stable sorting option in
the standard library. We could introduce a separate stable function(s) for
this purpose, but I believe we can just as well make all our existing sorts
stable.

This does not require actually switching sorting algorithms to something
like Timsort. We can essentially do the same as the above PHP code, just
much more efficiently. Due to certain implementation details, we can do
this without memory usage increase, and with minimal performance impact.
I've put https://github.com/php/php-src/pull/5236 up as a prototype.

The only issue I ran into is that this change has a negative impact on code
using illegal comparison callbacks like this:

usort($array, function($a, $b) {
    return $a > $b;
});

The return value of the sorting callback should be $a <=> $b, but using $a
> $b also works right now, due to implementation details of the sorting
implementation (only the outcome of $compare($a, $b) > 0 ends up being used
by the sort).

This kind of incorrect code will break under the proposed implementation,
because we will now compare by original position if the comparison function
reports equality. Because the comparator reports equality inconsistently
(it says that $a == $b, but $b != $a), the sort results are also
inconsistent.

What do people think about this? Is there interest in making sorting
stable? Is it okay to break code using illegal comparison callbacks?

Regards,
Nikita

--000000000000cf953905a00a1a16--