Stable Sorting in PHP with the Schwartzian Transform

You have an array:

$object0 = (object)array('priority' => 5);
$object1 = (object)array('priority' => 10);
$object2 = (object)array('priority' => 5);
$my_array = array(
  0 => $object0,
  1 => $object1,
  2 => $object2,
);

Now let’s say you want to sort that array. You would probably call uasort($my_array $callback) with a callback to sort by the objects’ priority property. And you might end up with:

$my_array == array(
  0 => $object0,
  2 => $object2,
  1 => $object1,
);

Or, you might end up with:

$my_array == array(
  2 => $object2,
  0 => $object0,
  1 => $object1,
);

Keep calling uasort($my_array, $callback), and you might even switch back and forth between the two. What if you want to maintain the order of $object0 and $object2, no matter how many times you sort the array? There’s no native PHP function to accomplish this, but it’s fairly easily done using the Schwartzian Transform.

The Schwartzian Transform is a three step process: decorate, sort, undecorate. We decorate each item in the array by wrapping it in a more-easily sorted container. We then sort those containers, then remove our wrapper, leaving us with our original elements, only sorted.

For our array above, we would transform each item in the array into an array with three items: the priority, the index, and the the object.

array_walk( $my_array, create_function( '&$v, $k' , '$v = array( $v->priority, $k, $v );'));

PHP’s built-in asort() sorts this first by priority (array index 0), and if priorities are the same, then items by index (array index 1). Since every index is distinct, the sorting will never fall back to the third item in the array.

asort($my_array);

Finally, put all the items in the array back where we found them:

array_walk( $my_array, create_function( '&$v, $k', '$v = $v[2];'));

The Schwartzian Transform has the benefits of being both stable (multiple calls will produce the same result) and efficient (you only have to calculate the “priority” of each item once; helpful if it’s a more expensive operation).

Comments are closed.