|  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #40888 Sorts should be stable
Submitted: 2007-03-22 08:00 UTC Modified: 2018-03-12 12:21 UTC
Avg. Score:4.6 ± 0.5
Reproduced:9 of 9 (100.0%)
Same Version:2 (22.2%)
Same OS:3 (33.3%)
From: jo at durchholz dot org Assigned: cmb (profile)
Status: Duplicate Package: Arrays related
PHP Version: 4.4.5 OS: Irrelevant
Private report: No CVE-ID: None
 [2007-03-22 08:00 UTC] jo at durchholz dot org
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...


Add a Patch

Pull Requests

Add a Pull Request


AllCommentsChangesGit/SVN commitsRelated reports
 [2009-10-22 20:25 UTC] mac at macnewbold dot com
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.
 [2016-12-31 00:10 UTC]
-Package: Feature/Change Request +Package: Arrays related
 [2018-03-12 12:21 UTC]
-Status: Open +Status: Duplicate -Assigned To: +Assigned To: cmb
 [2018-03-12 12:21 UTC]
Duplicate of request #53341.
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Jul 25 16:01:28 2024 UTC