PHP usort() order in case of equality

Question

In the PHP manual for usort(), it states:

If two members compare as equal, their relative order in the sorted array is undefined.

Also,

A new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal.

Then my question is: what happens if two elements are equal (e.g. the user defined function returns 0)? I am using this function and apparently equal items are arranged randomly in the sorted array.

Answer 1

Be careful not to confuse "undefined" and "random".

A random implementation would indeed be expected to give a different ordering every time. This would imply there was specific code to shuffle the results when they're found to be equal. This would make the algorithm more complex and slower, and rarely be a desirable outcome.

What undefined means is the opposite: absolutely no care has been taken while designing the algorithm to have predictable or stable order. This means the result may be different every time you run it, if that happens to be the side effect of the algorithm on that data.

You can see the core sort implementation in the PHP source code. It consists of a mixture of "quick sort" (divide and conquer) and insertion sort (a simpler algorithm effective on short lists) with hand-optimised routines for lists of 2, 3, 4, and 5 elements.

So the exact behaviour of equal members will depend on factors like the size of the list, where in the list those equal members come, how many equal members there are in one batch, and so on. In some situations, the algorithm will see that they're identical, and not swap them (the ideal, because swapping takes time); in others, it won't directly compare them until they've already been moved relative to other things, so they'll end up in a different order.

Answer 2

I also find the same while sorting my array, then I found some custom made function because php have some limitation to use defined sorting function .

http://php.net/manual/en/function.uasort.php#Vd114535

PHP 7 uses a stable sort algorithm for small arrays (< 16), but for larger arrays the algorithm is still not stable. Furthermore PHP makes no guarantee whether sorting with *sort() is stable or not https://bugs.php.net/bug.php?id=53341.