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.

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.

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