PHP usort() order in case of equality

Question

In the PHP manual for usort(), it states:

If two members compare as equal, their relative order in the sorted array is undefined.

Also,

A new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal.

Then my question is: what happens if two elements are equal (e.g. the user defined function returns 0)? I am using this function and apparently equal items are arranged randomly in the sorted array.

Answer 1

Be careful not to confuse "undefined" and "random".

A random implementation would indeed be expected to give a different ordering every time. This would imply there was specific code to shuffle the results when they're found to be equal. This would make the algorithm more complex and slower, and rarely be a desirable outcome.

What undefined means is the opposite: absolutely no care has been taken while designing the algorithm to have predictable or stable order. This means the result may be different every time you run it, if that happens to be the side effect of the algorithm on that data.

You can see the core sort implementation in the PHP source code. It consists of a mixture of "quick sort" (divide and conquer) and insertion sort (a simpler algorithm effective on short lists) with hand-optimised routines for lists of 2, 3, 4, and 5 elements.

So the exact behaviour of equal members will depend on factors like the size of the list, where in the list those equal members come, how many equal members there are in one batch, and so on. In some situations, the algorithm will see that they're identical, and not swap them (the ideal, because swapping takes time); in others, it won't directly compare them until they've already been moved relative to other things, so they'll end up in a different order.

Answer 2

I also find the same while sorting my array, then I found some custom made function because php have some limitation to use defined sorting function .

http://php.net/manual/en/function.uasort.php#Vd114535

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 https://bugs.php.net/bug.php?id=53341.

Answer 3

If I have an array of: ['b', 'a', 'c', 'b'] and I were to sort this I would get: ['a','b','b','c']. Since 'b' == 'b' php can not guarantee that one comes before the other so the sort order is 'undefined', however since they are equal, does this matter?

If you are using a sort function that returns 0 for unequal objects you're facing a different problem altogether.

Answer 4

understand that php does not care about the order if all the compared values are same.

Example:

$temp=array("b"=>"10","c"=>"10","d"=>"10","e"=>"4");

as above array has 4 array length in which 3 are having the same values as shown b,c,d = 10; arsort() //The arsort() function sorts an associative array in descending order, according to the value

if print_r(arsort($temp)) o/p: => Array ( [b] => 10 [c] => 10 [d] => 10 [e] => 4 )

this means it return array after sorting equal value but keeps the position(order) same for equal values

but

if $temp=array("a"=>"4",b"=>"10","c"=>"10","d"=>"10","e"=>"4"); here in above array b,c,d = 10 are bounded under two extreme left and right arrays having value less then center (b,c,d = 10) values

the arsort of above temp is o/p: Array ( [c] => 10 [b] => 10 [d] => 10 [a] => 4 [e] => 4 )

it gives the middle part i.e [c] array in center. this means if similar values or equal values array is bounded by from both side by lower values array or the first value is lower then the order of equal gives middle one from three array values as first in that three .

Answer 5

I was also facing the same problem, where 2 rows have same values and when apply sort function its order gets changed which I didn't want. I want to sort keys based on their values, if they are equal don't change order. So here is my solution-

// sample array 
$arr = Array("a" => 0.57,"b" => 1.19,"c" => 0.57,"d" => 0.57,"e" => 0.57,"f" => 0.57,"g" => 0.57,"h" => 0.57,"i" => 0.99,"j" => 1.19,"k" => 1.19);
    $multi_arr = [];
    foreach ($arr as $k=>$val){
       $multi_arr["$val"][] = array($k=>$val); 
    }
    uksort($multi_arr, function ($a, $b) { 
                    return $b > $a ? 1 : -1;
            });
    $s_arr = [];
    foreach ($multi_arr as $k=>$val){
        foreach($val as $p_id){         
            $p_arr = array_keys($p_id);
            $s_arr[] = $p_arr[0]; 
        }
    }
print_r($s_arr);

output-

Array([0] => b,[1] => j,[2] => k,[3] => i,[4] => a,[5] => c,[6] => d,[7] => e,[8] => f,[9] => g,[10] => h)

Answer 6

This function preserves order for equal values (example from my CMS EFFCORE):

function array_sort_by_number(&$array, $key = 'weight', $order = 'a') {
  $increments = [];
  foreach ($array as &$c_item) {
    $c_value = is_object($c_item) ? $c_item->{$key} : $c_item[$key];
    if ($order === 'a') $increments[$c_value] = array_key_exists($c_value, $increments) ? $increments[$c_value] - .0001 : 0;
    if ($order === 'd') $increments[$c_value] = array_key_exists($c_value, $increments) ? $increments[$c_value] + .0001 : 0;
    if (is_object($c_item)) $c_item->_synthetic_weight   = $c_value + $increments[$c_value];
    else                    $c_item['_synthetic_weight'] = $c_value + $increments[$c_value];
  }
  uasort($array, function ($a, $b) use ($order) {
    if ($order === 'a') return (is_object($b) ? $b->_synthetic_weight : $b['_synthetic_weight']) <=> (is_object($a) ? $a->_synthetic_weight : $a['_synthetic_weight']);
    if ($order === 'd') return (is_object($a) ? $a->_synthetic_weight : $a['_synthetic_weight']) <=> (is_object($b) ? $b->_synthetic_weight : $b['_synthetic_weight']);
  });
  foreach ($array as &$c_item) {
    if (is_object($c_item)) unset($c_item->_synthetic_weight);
    else                    unset($c_item['_synthetic_weight']);
  }
  return $array;
}

It works with both arrays and objects. It adds a synthetic key, sorts by it, and then removes it.

Test

$test = [
  'a' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'e' => ['weight' =>  4],
];
$test_result = [
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'a' => ['weight' =>  4],
  'e' => ['weight' =>  4],
];
array_sort_by_number($test, 'weight', 'a');
print_R($test);
var_dump($test === $test_result);

$test = [
  'a' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'e' => ['weight' =>  4],
];
$test_result = [
  'a' => ['weight' =>  4],
  'e' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
];
array_sort_by_number($test, 'weight', 'd');
print_R($test);
var_dump($test === $test_result);