Recently, one of the php lists I'm on was asked how to implement a stable sort using php's sort functions. But since all of php's sort functions eventually seem to land up in zend_qsort, the default sort is not stable. The query on list had this simple example which illustrates the problem clearly.
bash$ php -r '$a= array(1,1,1); asort($a); print_r($a);'
Array
(
[2] => 1
[1] => 1
[0] => 1
)
The basic problem here is to produce a stable sort which still operates in quicksort O(n*lg(n)) time. Essentially, falling back onto a bubble sort is ... well ... giving up :)
Schwartzian transform: The programming idiom, named after Randal L. Schwartz, is a carry-over of the decorate-sort-undecorate lisp memoization into perl. The real problem here however was putting it into a php syntactic form which was clean and as similar to the original as possible. For example, here's how the python version of the code would look like (despite the fact that the current python sort is stable).
a = [1,1,1] b = zip(a, range(len(a))) # decorate b.sort() # sort a = map(lambda x : x[0], b) # undecorate
array_walk() magic: Coming from a world of constant iterators, I had read the array_walk documentation and sort of read the "Users may not change array itself ..." as boilerplate. But as it turns out, the callback function is allowed to change the current value *in place* and for that purpose it gets a reference to the value. With that in mind, array_walk becomes a faux in-place map/transform function.
$a = array(1,1,1);
function dec(&$v, $k) { $v = array($v, $k);}
function undec(&$v, $k) { $v = $v[0]; }
array_walk($a, dec); // decorate
asort($a); // sort
array_walk($a, undec); // undecorate
And there you have it, a lispism made famous by perl, implemented nearly exactly in php.
--Whoever knows he is deep, strives for clarity;
Whoever would like to appear deep to the crowd, strives for obscurity.
-- Nietzsche