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: 2020-08-13 09:27 UTC
Votes:53
Avg. Score:4.5 ± 0.8
Reproduced:48 of 49 (98.0%)
Same Version:17 (35.4%)
Same OS:24 (50.0%)
From: goetas at lignano dot it Assigned: nikic (profile)
Status: Closed Package: Arrays related
PHP Version: 5.3.3 OS: any
Private report: No CVE-ID: None
 [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>
 [2019-12-09 14:03 UTC] michael dot vorisek at email dot cz
I accept that it is not a bug, but what about offering the stable quarantee in PHP 8.0? Timsort is used more and more across the industry and except it needs more line of code, it does not perferm worse than quicksort.

Timsort is now also the default algorithm in Python, Java 7, ...

This will also go hand-in-hand with the PHP philosophy to have only one universal thing.

How can I propose this improvement? Can I have a feedback from the PHP core team?

Sources:
- https://stackoverflow.com/questions/7770230/comparison-between-timsort-and-quicksort
- https://en.wikipedia.org/wiki/Timsort
 [2020-03-06 10:32 UTC] nikic@php.net
-Assigned To: +Assigned To: nikic
 [2020-08-13 09:27 UTC] nikic@php.net
-Status: Assigned +Status: Closed
 [2020-08-13 09:27 UTC] nikic@php.net
All sorting functions are stable as of PHP 8.0.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Tue Mar 19 02:01:28 2024 UTC