Sorting in JavaScript: Should every compare function have a “return 0” statement?

by

So I was wondering if there is any advantage on omitting a return 0 statement.

Less letters to type. And it might be a tiny bit faster due to the one omitted comparison. All other effects are disadvantages.

I realized that on MDN, it also says:

Note: the ECMAscript standard does not guarantee this behaviour, and
thus not all browsers (e.g. Mozilla versions dating back to at least
2003) respect this.

referring to the behavior, that a and b should remain unchanged if 0
is returned.

That the position of a and b may remain unchanged is only the requirement for a stable sort. This is not a specified behaviour, and some browsers have implemented a non-stable sort algorithm.

However, the actual purpose of returning zero is that neither a is sorted before b (as if less than 0) nor that b is sorted before a (as if greater than 0) – basically when a equals b. This is a must-have for a comparison, and all sorting algorithms obey it.

To produce a valid, satisfiable ordering (mathematically: divide the items into totally ordered equivalence classes), a comparison must have certain properties. They are listed in the spec for sort as requirements for a “consistent comparison function“.

The most prominent one is reflexivity, demanding that an item a is equal to a (itself). Another way to say this is:

compare(a, a) must always return 0

What happens when a comparison function does not satisfy this (like the one you stumbled upon obviously does)?

The spec says

If comparefn […] is not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.

which basically means: If you provide an invalid comparison function, the array will probably not be sorted correctly. It might get randomly permuted, or the sort call might not even terminate.

So maybe, by returning 0, we get a slightly different
sorted array in different browsers? Could that be a reason?

No, by returning 0 you get a correctly sorted array across browsers (which might be different due to the unstable sort). The reason is that by not returning 0 you get slightly different permuted arrays (if at all), maybe even producing the expected result but usually in a more complicated manner.

So what could happen if you don’t return 0 for equivalent items? Some implementations have no problems with this, as they never compare an item to itself (even if apparent at multiple positions in the array) – one can optimise this and omit the costly call to the compare function when it is already known that the result must be 0.

The other extreme would be a never-terminating loop. Assuming you had two equivalent items after each other, you would compare the latter with the former and realise that you had to swap them. Testing again, the latter would still be smaller than the former and you’d have to swap them again. And so on…

However, an efficient algorithm mostly does not test already compared items again, and so usually the implementation will terminate. Still, it might do more or less swaps that actually had been unnecessary, and will therefore take longer than with a consistent comparison function.

And are there any other good reasons for not returning zero at all?

Being lazy and hoping that the array does not contain duplicates.

More Related Contents:

  1. Sorting array of object based on range of Numbers of String [closed]
  2. Convert string into several integer arrays [duplicate]
  3. Sort array of objects by string property value
  4. Sort JavaScript object by key
  5. Sorting in JavaScript: Shouldn’t returning a boolean be enough for a comparison function?
  6. How to sort 2 dimensional array by column value?
  7. How do you sort an array on multiple columns?
  8. How can I convert the “arguments” object to an array in JavaScript?
  9. How to sort array inside collection record in MongoDB?
  10. Console.log showing only the updated version of the object printed
  11. Sort an array of object by a property (with custom order, not alphabetically)
  12. Sorting a JSON object in Javascript
  13. Sorting objects by property values
  14. Simple function to sort an array of objects
  15. How to sort an associative array by its values in Javascript?
  16. using lodash .groupBy. how to add your own keys for grouped output?
  17. Sort an array based on another array of integers
  18. How to sort an array based on the length of each element?
  19. Any way to extend javascript’s array.sort() method to accept another parameter?
  20. jQuery sort elements using data id
  21. Reordering arrays
  22. Javascript array sort and unique
  23. How can I compare software version number using JavaScript? (only numbers)
  24. sort outer array based on values in inner array, javascript
  25. Javascript: Sort array and return an array of indices that indicates the position of the sorted elements with respect to the original elements
  26. Sorting an Array of JavaScript Objects a Specific Order (using existing function)
  27. Sorting a list by data-attribute
  28. Sort a table fast by its first column with Javascript or jQuery
  29. Algorithm of JavaScript “sort()” Function
  30. How to sort an array of objects by date?

Leave a Comment