Sorting in JavaScript: Should Every Compare Function Have a "Return 0" Statement

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

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.

Sorting an array by returning 1 or 0 or -1 if it returns these values how the sort function can decide which one to put first

The (a,b) is a compare function which we pass in sort.
Consider the following example:

let numbers = [0, 1 , 2, 3, 10, 20, 30 ];
numbers.sort();
console.log(numbers);

The output is:
[ 0, 1, 10, 2, 20, 3, 30 ]

So to fix the above issue we pass (a,b) for sorting.

If compare(a,b) is less than zero, the sort() method sorts a to a lower index than b. In other words, a will come first.
If compare(a,b) is greater than zero, the sort() method sort b to a lower index than a, i.e., b will come first.
If compare(a,b) returns zero, the sort() method considers a equals b and leaves their positions unchanged.

If you want to know more about sort in js in details :
https://www.javascripttutorial.net/javascript-array-sort/

Why does compare function of sort() work like that?

Your interpreation of the docs is wrong.

You say

-1 means elements should stay in the same place.

That's wrong, the docs just state that -1 means a should be sorted before b.

Depending on the underlying sorting algorithm, there is no guarantee whatsoever that, when calling the comparefunction with parameters a and b that a is currently before b in the array. Ie imagine an array [1,2,3]. It may be possible that the compare function is called with parameters (3, 1) or (1,3). But if you return -1 in the first case, 1 and 3 will indeed switch positions. And vice versa, if you return 1 in the second case, 1 and 3 will again switch places.

EDIT

Different browser implement sort differently. For instance if you execute the following snippet in chrome and in firefox you will get different results.

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort((a,b) => {
    console.log(`${a}  ${b}`);
  return 1;
})
console.log(arr);

How does sort function work in JavaScript, along with compare function

The "compare" function must take two arguments, often referred to as a and b. Then you make the compare function return 0, greater than 0, or less than 0, based on these values, a and b.

1. Return greater than 0 if a is greater than b
2. Return 0 if a equals b
3. Return less than 0 if a is less than b

With these three return values, and only two arguments, it is possible to write a compare function that can sort any type of input data type, or complex data structures.

Then, when you call sort(), with your custom compare function, the compare function is called on pairs in your to-be-sorted list, to determine the proper ordering.

Lets walk through a simple example... Suppose you're only sorting some numbers, so we have a very simple compare function:

function compare(a,b) {
    return a - b;
}

Simply subtracting b from a will always return greater than zero if a is larger than b, 0 if they are equal, or less than zero if a is less than b. So it meets the requirements for a compare function.

Now lets suppose this is our list of numbers to sort:

var numbers = [1,5,3.14];

When you call numbers.sort(compare), internally it will actually execute:

compare(1,5);     // Returns -4, a is less than b
compare(1,3.14);  // Return -2.14, a is less than b
compare(5,3.14);  // returns 1.86, a is greater than b

If you've ever done manual sorting or alphabetizing, you've done precisely the same thing, probably without realizing it. Even though you may have dozens or hundreds of items to compare, you're constantly comparing only two numbers (or author's last names, or whatever) at a time. Going through or short list of three numbers again, you'd start by comparing the first two numbers:

1. Is 1 greater than or less than 5? Less than, so put these two numbers in our list: 1,5
2. Is 3.14 greater than or less than 1? Greater than, so it goes after 1 in the new list
3. Is 3.14 greater than or less than 5 in our new list? Less than, so it goes before 5. Our new list is now [1,3.14,5]

Because you can provide your own compare() function, it is possible to sort arbitrarily complex data, not just numbers.

What does the return type 1, -1 and 0 do in a sort function?

It's Array.sort and has nothing to do with jQuery. Remember that jQuery is yet another library developed in javascript.

The MDN explains this already:

If compareFunction is supplied, the array elements are sorted
according to the return value of the compare function. If a and b are
two elements being compared, then:

1. If compareFunction(a, b) is less than 0, sort a to a lower index than
   b, i.e. a comes first.

2. If compareFunction(a, b) returns 0, leave a and
   b unchanged with respect to each other, but sorted with respect to all
   different elements. 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.

3. If compareFunction(a, b)
   is greater than 0, sort b to a lower index than a.

4. compareFunction(a, b) must always return the same value when given a specific pair of
   elements a and b as its two arguments. If inconsistent results are
   returned then the sort order is undefined

It's not mandatory to return only -1 or 1.

Why does points.sort(function(a, b){return a-b}); return -1, 0 or 1?

The sort callback has to return

• a negative number if a < b
• 0 if a === b
• a positive number if a > b

Three possible return values are needed because the sort function needs to know whether a is smaller than, equal to, or larger than b in order to correctly position a in the result array.

It is very common to just return -1, 0 and 1 if you working with non-numerical data (I guess that's why W3Schools mentions it). But if you use numerical data, you can simply subtract the values because

• if a < b then a - b < 0, i.e. a negative number
• if a === b then a - b === 0, i.e. 0
• if a > b then a - b > 0, i.e. a positive number

---

W3Schools is not very precise which is one of the reason why you should avoid it. Use MDN instead.

Can the qsort comparison function always return a non-zero value?

C 2018 7.22.5 4 says:

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key.

A total order requires that a = a. (To see this from the definition in the Wikipedia page: Connexity says, for any a and b, a ≤ b or b ≤ a. Substituting a for b gives a ≤ a or a ≤ a. So a ≤ a. Then the condition of antisymmetry is satisfied: We have a ≤ a and a ≤ a, so a = a.)

---

Related Topics