ID: 40888
Comment by: mac at macnewbold dot com
Reported By: jo at durchholz dot org
Status: Open
Bug Type: Feature/Change Request
Operating System: Irrelevant
PHP Version: 4.4.5
New Comment:
I don't see any feedback about this very old bug. It is clearly
possible to have a stable sort available in PHP, and clearly more
efficient to offer it in-core rather than at the user level. Is this
simply a WONTFIX?
Philosophically, I strongly believe that the developer should be the
one to decide whether they want to use a less efficient stable sort or a
more efficient but unstable sort on a case by case basis, not the
language designers. As it stands, we're all forced to use much less
efficient solutions when we require a stable sort.
Previous Comments:
------------------------------------------------------------------------
[2007-03-22 08:00:37] jo at durchholz dot org
Description:
------------
The manual says this on sorting:
"If two members compare as equal, their order in the sorted array is
undefined. Up to PHP 4.0.6 the user defined functions would keep the
original order for those elements, but with the new sort algorithm
introduced with 4.1.0 this is no longer the case as there is no solution
to do so in an efficient way."
Bug #18299 requests that the old ("stable") sort behavior be restored.
This is denied on the grounds that there is no efficient implementation
for that.
Now it *is* possible to stabilize any sort algorithm, by comparing key
positions if values compare equal.
Um, well, I can imagine that it's inefficient to determine the position
of a key. In that case, I'd propose to introduce a SORT_STABLE flag and
have the engine create a key=>position array when sorting with
SORT_STABLE.
That would still be more efficient than trying to stabilize the sort at
the PHP level. There, I'd have to do the following to get a stable
sort:
* Make a copy of the array,
wrapping each value in an array ($position, $value)
* Sort with a user-defined function. Have that function compare
$values, and if these compare equal, compare $positions.
* Unwrap the $values from the resulting sorted array.
In effect, this means the engine will have to construct and garbage
collect an array for each array element, so this is horribly inefficient
compared to any in-engine solution...
------------------------------------------------------------------------
--
Edit this bug report at http://bugs.php.net/?id=40888&edit=1
