php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #53341 Add a stable sorting flag to sort functions (uasort)
Submitted: 2010-11-18 11:11 UTC Modified: 2016-06-14 12:45 UTC
Votes:48
Avg. Score:4.5 ± 0.8
Reproduced:44 of 44 (100.0%)
Same Version:21 (47.7%)
Same OS:25 (56.8%)
From: goetas at lignano dot it Assigned:
Status: Open Package: Arrays related
PHP Version: 5.3.3 OS: any
Private report: No CVE-ID: None
Password:
Status:
Package:
Bug Type:
Summary:
From: goetas at lignano dot it
New email:
PHP Version: OS:

 

 [2010-11-18 11:11 UTC] goetas at lignano dot it
Description:
------------
Starting from php 4.1.0 the sorting of arrays is not stable.
With current sort method is not possible to sort two or more times (with different sort functions) an array with consistent result.

My suggestion is to add a flag to *sort functions to choose the sorting algorithm.

I'm not a c programmer, but i think that can be changed a behavior of zend_qsort with some parameters or add a mergesort that can be used if stable sort is required.



Test script:
---------------
<?php

$a = array(
	array("l"=>"B", "n"=>2),
	array("l"=>"A", "n"=>1),
	array("l"=>"C", "n"=>3),
	array("l"=>"E", "n"=>5),
	array("l"=>"D", "n"=>4),
);

usort($a, function($a1, $a2){ // alpha sort
	return strcmp($a1["l"],$a2["l"]);
});

usort($a, function($a1, $a2){ // sort odd first
	if($a1["n"]%2===0 && $a2["n"]%2!==0){
		return -1;
	}elseif($a2["n"]%2===0 && $a1["n"]%2!==0){
		return 1;
	}else{
		return 0;
	}
});

print_r($a);



Expected result:
----------------
Array
(
    [0] => Array
        (
            [l] => B
            [n] => 2
        )

    [1] => Array
        (
            [l] => D
            [n] => 4
        )

    [2] => Array
        (
            [l] => A
            [n] => 1
        )

    [3] => Array
        (
            [l] => C
            [n] => 3
        )

    [4] => Array
        (
            [l] => E
            [n] => 5
        )

)

Actual result:
--------------
Array
(
    [0] => Array
        (
            [l] => D
            [n] => 4
        )

    [1] => Array
        (
            [l] => B
            [n] => 2
        )

    [2] => Array
        (
            [l] => E
            [n] => 5
        )

    [3] => Array
        (
            [l] => C
            [n] => 3
        )

    [4] => Array
        (
            [l] => A
            [n] => 1
        )

)


Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2014-03-04 15:43 UTC] cw at clement dot hk
You can use this before the bug is fixed.

Clement Wong

function stable_uasort(&$array, $cmp_function) {
	if(count($array) < 2) {
		return;
	}
	$halfway = count($array) / 2;
	$array1 = array_slice($array, 0, $halfway, TRUE);
	$array2 = array_slice($array, $halfway, NULL, TRUE);

	stable_uasort($array1, $cmp_function);
	stable_uasort($array2, $cmp_function);
	if(call_user_func($cmp_function, end($array1), reset($array2)) < 1) {
		$array = $array1 + $array2;
		return;
	}
	$array = array();
	reset($array1);
	reset($array2);
	while(current($array1) && current($array2)) {
		if(call_user_func($cmp_function, current($array1), current($array2)) < 1) {
			$array[key($array1)] = current($array1);
			next($array1);
		} else {
			$array[key($array2)] = current($array2);
			next($array2);
		}
	}
	while(current($array1)) {
		$array[key($array1)] = current($array1);
		next($array1);
	}
	while(current($array2)) {
		$array[key($array2)] = current($array2);
		next($array2);
	}
	return;
}
 [2015-05-08 21:23 UTC] cmb@php.net
While there might be use cases demanding a stable sort, this is
clearly none of them. Just sort the array with a single usort(),
what is faster, by the way:

    <?php
    
    $a = array(
            array("l"=>"B", "n"=>2),
            array("l"=>"A", "n"=>1),
            array("l"=>"C", "n"=>3),
            array("l"=>"E", "n"=>5),
            array("l"=>"D", "n"=>4),
    );
    
    usort($a, function($a1, $a2){ // sort even first
            if($a1["n"]%2===0 && $a2["n"]%2!==0){
                    return -1;
            }elseif($a2["n"]%2===0 && $a1["n"]%2!==0){
                    return 1;
            }else{// alpha sort
                    return strcmp($a1["l"],$a2["l"]);
            }
    });
    
    print_r($a);
 [2015-08-13 12:59 UTC] cw at clement dot hk
Please note that this is fixed since PHP 7, so this issue can be close now.
 [2015-08-13 13:31 UTC] cmb@php.net
AFAIK PHP 7 uses a stable sort algorithm for small arrays (< 16),
but for larger arrays the algorithm is still not stable.
Furthermore PHP makes no guarantee whether sorting with *sort() is
stable or not.
 [2016-01-29 15:12 UTC] cw at clement dot hk
@cmb, this is more like a feature request than a bug report.
 [2016-06-14 12:31 UTC] mdg12v at gmail dot com
this bug still appears on php 7.0.6, it was working right on php 5.6.
magento totals sorting component calculating wrong total because of this bug. 
i bet many places affected because of this bug
 [2016-06-14 12:45 UTC] cmb@php.net
> this bug still appears on php 7.0.6, […]

To make it clear: this is not a bug. The fact that PHP doesn't
make any guarantees about the stability of the sort order is a
deliberate design decision, which is clearly documented[1]:

| If any of these sort functions evaluates two members as equal
| then the order is undefined (the sorting is not stable).

[1] <http://php.net/manual/en/array.sorting.php>
 
PHP Copyright © 2001-2017 The PHP Group
All rights reserved.
Last updated: Sun Nov 19 01:31:42 2017 UTC