PHP usort reorders array the sort value is the same for all

Question

I'm using usort to sort an array with an associative array within each element.

When all of the values I am sorting on in the array are the same then it still changes the position of the elements in the array, is there a way to prevent this?

For example this:

array(
    array('name' => 'Ben', 'authn_weight' => 85.3),
    array('name' => 'Josh', 'authn_weight' => 85.3),
    array('name' => 'Fred', 'authn_weight' => 85.3)
);

May be changed to this:

array(
    array('name' => 'Josh', 'authn_weight' => 85.3),
    array('name' => 'Ben', 'authn_weight' => 85.3),
    array('name' => 'Fred', 'authn_weight' => 85.3)
);

This is the sort function:

private function weightSortImplementation($a, $b){ 
    $aWeight = $a['autn_weight'];
    $bWeight = $b['autn_weight'];

    if ($aWeight == $bWeight) {
        return 0;
    }
    return ($aWeight < $bWeight) ? 1 : -1;
}

I have checked that the weightSortImplementation function is always returning 0 showing that they are the same. So why is this still reordering the array?

That's an interesting issue. I just tested this, and after using `usort` the order was reversed. http://codepad.org/PRFpq8Ug — gen_Eric, Aug 28 '12 at 16:28
They must not be using a [stable sort](http://en.wikipedia.org/wiki/Sorting_algorithm#Stability), which makes no guarantees about the order of elements if they are equal. — JoeyJ, Aug 28 '12 at 16:32

Ja͢ck · Accepted Answer · 2012-08-30T00:24:55.013

13

Aha, a case for the Schwartzian Transform.

It basically consists of three steps:

decorate; you turn every value into an array with the value as the first element and the key/index as the second
sort (as per normal)
undecorate; you reverse step 1

Here it is (I've tweaked it to your particular use case):

function decorate(&$v, $k)
{
    $v['authn_weight'] = array($v['authn_weight'], $k);
}

function undecorate(&$v, $k)
{
    $v['authn_weight'] = $v['authn_weight'][0];
}

array_walk($a, 'decorate');
usort($a, 'weightSortImplementation');
array_walk($a, 'undecorate');

The trick is in the following assertion:

array($x, 0) < array($x, 1)

This is what keeps the correct order of your array. And, no recursion required :)

edited Aug 30 '12 at 00:24

answered Aug 28 '12 at 16:52

Ja͢ck

170,779
38
263
309

super stuff bro.. !! – Mithun Satheesh Nov 21 '13 at 06:41
Hmm seems that this does not work for me on PHP 5.4. – Jens Kohl Feb 05 '15 at 08:44
@JensKohl Do you have a reproducible test script I could look at? – Ja͢ck Feb 05 '15 at 08:45
1

@JensKohl Ah, you can't do an `strcmp()` on an array ;-) you may want to check my [more elaborate answer](http://stackoverflow.com/questions/17364127/reference-all-basic-ways-to-sort-arrays-and-data-in-php/17365409#17365409) on the subject of stable sort. – Ja͢ck Feb 05 '15 at 08:56
@Ja͢ck I had to reread your answer several times but it made click and now it's working for me. Thanks. – Jens Kohl Feb 05 '15 at 09:16
This is genius, and really got me out of a pickle - seems to work perfectly. TY – Nate Jul 08 '19 at 09:26

score 9 · Answer 2 · answered Aug 28 '12 at 16:25

From the documentation:

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

You can use this function [source] that preserves order in the case of two elements being equal:

function mergesort(&$array, $cmp_function = 'strcmp') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) return;
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergesort($array1, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}

Is there any way to prevent this? Maybe using different sorting methods? or changing the sort implementation, I suppose could I get the weight sort to return either 1 or -1 if they are the same? — Chris, Aug 28 '12 at 16:28
I think you should attribute your source. I found this method duplicated [here](http://stackoverflow.com/a/4353844/135101). — Tyler Collier, Mar 02 '15 at 05:26

PHP usort reorders array the sort value is the same for all

2 Answers2

Linked