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?

Chlorobenzene

That's an interesting issue. I just tested this, and after using usort the order was reversed. codepad.org/PRFpq8Ug – Bumper

They must not be using a stable sort, which makes no guarantees about the order of elements if they are equal. – Mena

Answer 1

Aha, a case for the Schwartzian Transform.

It basically consists of three steps:

1. decorate; you turn every value into an array with the value as the first element and the key/index as the second
2. sort (as per normal)
3. 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 :)

Intensity

super stuff bro.. !! – Airplane

Hmm seems that this does not work for me on PHP 5.4. – Fauver

@JensKohl Do you have a reproducible test script I could look at? – Kassab

@JensKohl Ah, you can't do an strcmp() on an array ;-) you may want to check my more elaborate answer on the subject of stable sort. – Kassab

@Intensity I had to reread your answer several times but it made click and now it's working for me. Thanks. – Fauver

This is genius, and really got me out of a pickle - seems to work perfectly. TY – Cerveny

Answer 2

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;
} 

Pother

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? – Chlorobenzene

I think you should attribute your source. I found this method duplicated here. – Crabbed