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

Solution 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.

Solution 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

Solution 3:

For future reference, I've put a set of stable sort variants of builtin PHP functions on Github: https://github.com/vanderlee/PHP-stable-sort-functions, based on @Jack's solution and a few other tricks.