|  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #45988 usort assumes comparison operation is transitive
Submitted: 2008-09-03 20:38 UTC Modified: 2008-09-04 17:44 UTC
From: php at sameprecision dot org Assigned:
Status: Not a bug Package: Arrays related
PHP Version: 5.2.6 OS: irrelevant
Private report: No CVE-ID: None
View Add Comment Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
You can add a comment by following this link or if you reported this bug, you can edit this bug over here.
Block user comment
Status: Assign to:
Bug Type:
From: php at sameprecision dot org
New email:
PHP Version: OS:


 [2008-09-03 20:38 UTC] php at sameprecision dot org
Using usort, not all pairs of elements are compared.  If a comparison operation is not transitive, this leads to unexpected ordering, even though every pair of elements are comparable.
This should probably be mentioned in the documentation.

Reproduce code:
//goal: sort $array so that an element is not a substring of any subsequent elements

$array = array('aa','b','a');

//if $a is a substring of $b, return 1.  Else return -1
function compare($a,$b){
   return strpos($b,$a)===false ? -1 : 1;



Expected result:
Array ( [0] => aa [1] => b [2] => a )

Actual result:
Array ( [0] => a [1] => b [2] => aa )


Add a Patch

Pull Requests

Add a Pull Request


AllCommentsChangesGit/SVN commitsRelated reports
 [2008-09-04 17:44 UTC] php at sameprecision dot org
I think I have made a mistake in trying to use a generalized sorting algorithm with a comparison operation that is not transitive.
The operation HAS to be transitive or there will always be an example that doesn't work.

PHP Copyright © 2001-2020 The PHP Group
All rights reserved.
Last updated: Sun Jul 12 14:01:25 2020 UTC