From: jo at durchholz dot org
Operating system: Irrelevant
PHP version: 4.4.5
PHP Bug Type: Feature/Change Request
Bug description: Sorts should be stable
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 bug report at http://bugs.php.net/?id=40888&edit=1
--
Try a CVS snapshot (PHP 4.4):
http://bugs.php.net/fix.php?id=40888&r=trysnapshot44
Try a CVS snapshot (PHP 5.2):
http://bugs.php.net/fix.php?id=40888&r=trysnapshot52
Try a CVS snapshot (PHP 6.0):
http://bugs.php.net/fix.php?id=40888&r=trysnapshot60
Fixed in CVS: http://bugs.php.net/fix.php?id=40888&r=fixedcvs
Fixed in release:
http://bugs.php.net/fix.php?id=40888&r=alreadyfixed
Need backtrace: http://bugs.php.net/fix.php?id=40888&r=needtrace
Need Reproduce Script: http://bugs.php.net/fix.php?id=40888&r=needscript
Try newer version: http://bugs.php.net/fix.php?id=40888&r=oldversion
Not developer issue: http://bugs.php.net/fix.php?id=40888&r=support
Expected behavior: http://bugs.php.net/fix.php?id=40888&r=notwrong
Not enough info:
http://bugs.php.net/fix.php?id=40888&r=notenoughinfo
Submitted twice:
http://bugs.php.net/fix.php?id=40888&r=submittedtwice
register_globals: http://bugs.php.net/fix.php?id=40888&r=globals
PHP 3 support discontinued: http://bugs.php.net/fix.php?id=40888&r=php3
Daylight Savings: http://bugs.php.net/fix.php?id=40888&r=dst
IIS Stability: http://bugs.php.net/fix.php?id=40888&r=isapi
Install GNU Sed: http://bugs.php.net/fix.php?id=40888&r=gnused
Floating point limitations: http://bugs.php.net/fix.php?id=40888&r=float
No Zend Extensions: http://bugs.php.net/fix.php?id=40888&r=nozend
MySQL Configuration Error: http://bugs.php.net/fix.php?id=40888&r=mysqlcfg
