Preserve key order (stable sort) when sorting with PHP's uasort

Question

This question is actually inspired from another one here on SO and I wanted to expand it a bit.

Having an associative array in PHP is it possible to sort its values, but where the values are equal to preserve the original key order, using one (or more) of PHP's built in sort function?

Here is a script I used to test possible solutions (haven't found any):

<?php
header('Content-type: text/plain');
for($i=0;$i<10;$i++){
    $arr['key-'.$i] = rand(1,5)*10;
}
uasort($arr, function($a, $b){
    // sort condition may go here //
    // Tried: return ($a == $b)?1:($a - $b); //
    // Tried: return $a >= $b; //
});
print_r($arr);
?>

Pitfall: Because the keys are ordered in the original array, please don't be tempted to suggest any sorting by key to restore to the original order. I made the example with them ordered to be easier to visually check their order in the output.

Telephotography

In other words, the solution to this question is a stable sorting algorithm, which none of PHP's sorting algorithms are, ostensibly. – Sekyere

I suspected that much, but I would like a definitive answer and/or a possible workaround. – Telephotography

Is there a reason to use biult-in functions only ? – Chariot

php.net/manual/en/array.sorting.php - If any of these sort functions evaluates two members as equal then the order is undefined (the sorting is not stable). – Capsulate

@Chariot First of all I would like to know if this is possible by using one of PHP's functions. Secondly I would like to see an alternative. – Telephotography

Please have a look at: notmysock.org/blog/php/schwartzian-transform.html it solves my problem. – Jaborandi

This entire page is now obsolete. See wiki.php.net/rfc/…. Stable sorting has been implemented 3 years ago. – Stereotypy

@Stereotypy Sadly, not everyone upgraded to PHP 8 yet. This page will eventually become irrelevant, but I think we're still far from that point. w3techs.com/technologies/details/pl-php – Telephotography

Those experiencing this problem and not yet operating on PHP8, will now know that they only need to modernize their stack to eliminate this irritation. – Stereotypy

Answer 1

Since PHP does not support stable sort after PHP 4.1.0, you need to write your own function.

This seems to do what you're asking: http://www.php.net/manual/en/function.usort.php#38827

As the manual says, "If two members compare as equal, their order in the sorted array is undefined." This means that the sort used is not "stable" and may change the order of elements that compare equal.

Sometimes you really do need a stable sort. For example, if you sort a list by one field, then sort it again by another field, but don't want to lose the ordering from the previous field. In that case it is better to use usort with a comparison function that takes both fields into account, but if you can't do that then use the function below. It is a merge sort, which is guaranteed O(n*log(n)) complexity, which means it stays reasonably fast even when you use larger lists (unlike bubblesort and insertion sort, which are O(n^2)).

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

---

Also, you may find this forum thread interesting.

Chariot

The forum thread is not interesting. The other parts or your answer are. – Telephotography

@Alin, that's why I wrote, "may find it interesting..." :) – Chariot

@Alin, actually it goes to a conclusion that all the methods described in that DON'T work. So, in a way, we know not to try those methods. Helpful in that sense. – Chariot

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

Please see @Martijn's answer, which uses decoration and uasort with a wrapped compare function, and takes 1/5th the time as this answer (which is a great illustration, but inneficient). – Rhythmics

$array2[0] fails if no such key exists. It seems this solution has a restriction that needs stating. – Amoebaean

Answer 2

array_multisort comes in handy, just use an ordered range as second array ($order is just temporary, it serves to order the equivalent items of the first array in its original order):

$a = [
  "key-0" => 5,
  "key-99" => 3,
  "key-2" => 3,
  "key-3" => 7
];

$order = range(1,count($a));
array_multisort($a, SORT_ASC, $order, SORT_ASC);

var_dump($a);

Output

array(4) {
  ["key-99"]=>
  int(3)
  ["key-2"]=>
  int(3)
  ["key-0"]=>
  int(5)
  ["key-3"]=>
  int(7)
}

I used test data with not-ordered keys to demonstrate that it works correctly. Nonetheless, here is the output your test script:

Array
(
    [key-1] => 10
    [key-4] => 10
    [key-5] => 20
    [key-8] => 20
    [key-6] => 30
    [key-9] => 30
    [key-2] => 40
    [key-0] => 50
    [key-3] => 50
    [key-7] => 50
)

Downside

It only works with predefined comparisons, you cannot use your own comparison function. The possible values (second parameter of array_multisort()) are:

Sorting type flags:

• SORT_ASC - sort items ascendingly.
• SORT_DESC - sort items descendingly.
• SORT_REGULAR - compare items normally (don't change types)
• SORT_NUMERIC - compare items numerically
• SORT_STRING - compare items as strings
• SORT_LOCALE_STRING - compare items as strings, based on the current locale. It uses the locale, which can be changed using setlocale()
• SORT_NATURAL - compare items as strings using "natural ordering" like natsort()
• SORT_FLAG_CASE - can be combined (bitwise OR) with SORT_STRING or SORT_NATURAL to sort strings case-insensitively

Compulsion

You may also use array_sort($a, SORT_ASC, array_keys($a), SORT_NATURAL) for a similar form of stable sorting. Which changes [ 'Sick' => 8, 'Vacation' => 12, 'Other' => -4, 'Holiday' => 0, 'Bereavement' => 0 ] to [ 'Other' => -4, 'Bereavement' => 0, 'Holiday' => 0, 'Sick' => 8, 'Vacation' => 12 ] – Emotionality

The sorting directions can be omitted. 3v4l.org/LtkIq – Stereotypy

Answer 3

For completeness sake, you should also check out the Schwartzian transform:

// decorate step
$key = 0;
foreach ($arr as &$item) {
        $item = array($item, $key++); // add array index as secondary sort key
}

// sort step
asort($arr); // sort it

// undecorate step
foreach ($arr as &$item) {
    $item = $item[0]; // remove decoration from previous step
}

The default sort algorithm of PHP works fine with arrays, because of this:

array(1, 0) < array(2, 0); // true
array(1, 1) < array(1, 2); // true

If you want to use your own sorting criteria you can use uasort() as well:

// each parameter is an array with two elements
// [0] - the original item
// [1] - the array key
function mysort($a, $b)
{
    if ($a[0] != $b[0]) {
        return $a[0] < $b[0] ? -1 : 1;
    } else {
        // $a[0] == $b[0], sort on key
        return $a[1] < $b[1] ? -1 : 1; // ASC
    }
}

Obligatory

Please note the Pitfall in the question. You should not rely on the keys to be ordered in the original array. – Telephotography

@AlinPurcaru Okay, fair enough. Edited :) – Cursor

Answer 4

This is a solution using which you can achieve stable sort in usort function

public function sortBy(array &$array, $value_compare_func)
{
    $index = 0;
    foreach ($array as &$item) {
        $item = array($index++, $item);
    }
    $result = usort($array, function($a, $b) use ($value_compare_func) {
        $result = call_user_func($value_compare_func, $a[1], $b[1]);
        return $result == 0 ? $a[0] - $b[0] : $result;
    });
    foreach ($array as &$item) {
        $item = $item[1];
    }
    return $result;
}

Semiconscious

Answer 5

As a workaround for stable sort:

<?php
header('Content-type: text/plain');
for ($i = 0;$i < 10;$i++)
{
    $arr['key-' . $i] = rand(1, 5) * 10;
}
uksort($arr, function ($a, $b) use ($arr)
{
    if ($arr[$a] === $arr[$b]) return array_search($a, array_keys($arr)) - array_search($b, array_keys($arr));
    return $arr[$a] - $arr[$b];
});
print_r($arr);

Secondbest

The 4x nested array_search/array_keys calls in the comparator really hurt from a time complexity standpoint. This answer essentially encodes the indices for the sort once before, then strips them off after which are both linear operations that don't damage the underlying complexity. On the other hand, walking the array for every comparison as shown here cranks it up to O(n * n * log(n))--worse than bubble sort but fine if you only have a few elements. – Banks

Answer 6

As of PHP8.0, this entire pages is obsolete. PHP performs a stable sort.

Given:

$array = array (
  'key-0' => 40,
  'key-1' => 50,
  'key-2' => 10,
  'key-3' => 20,
  'key-4' => 20,
  'key-5' => 30,
  'key-6' => 10,
  'key-7' => 20,
  'key-8' => 40,
  'key-9' => 40,
);

asort(): (Demo)

asort($array);
var_export($array);

uasort(): (Demo)

uasort($array, fn($a, $b) => $a <=> $b);
var_export($array);

Output (from either):

array (
  'key-2' => 10,
  'key-6' => 10,
  'key-3' => 20,
  'key-4' => 20,
  'key-7' => 20,
  'key-5' => 30,
  'key-0' => 40,
  'key-8' => 40,
  'key-9' => 40,
  'key-1' => 50,
)

Notice, now, that the values are sorted by value ascending and the original keys were left in their original positions - relative to other elements holding the same value.

Stereotypy

Answer 7

Just to complete the responses with some very specific case. If the array keys of $array are the default one, then a simple array_values(asort($array)) is sufficient (here for example in ascending order)

Shaer