Does Array.sort() not work the same in all browsers?

[Thomas Mlynarczyk]

While experimenting with Array.sort(function) I got different results from
different browsers. How can that be? Shouldn't I expect identical results -
given both the input array and the sort function are identical? What's wrong
here?

Greetings,
Thomas

 

[Douglas Crockford]

While experimenting with Array.sort(function) I got different results from

different browsers. How can that be? Shouldn't I expect identical results -
given both the input array and the sort function are identical? What's wrong
here?

Do you suppose you could share an example with us?

 

[Thomas Mlynarczyk]

Also sprach Douglas Crockford:

Do you suppose you could share an example with us?

Sure:

a = new Array(0,1,2,3,4,5,6,7,8,9);
a = a.sort(function(a,b){return a+3-b;});
t='';
for(i in a) t+= a;
alert(t);

IE5 says "1205643987"
Mozilla says "0142857639"
Opera7 says "1052438769"

So why do different browsers give different results with identical code?

 

[Douglas Crockford]

a = new Array(0,1,2,3,4,5,6,7,8,9);

a = a.sort(function(a,b){return a+3-b;});
t='';
for(i in a) t+= a;
alert(t);

IE5 says "1205643987"
Mozilla says "0142857639"
Opera7 says "1052438769"

So why do different browsers give different results with identical code?

Your comparison function is at fault, not the sort. The function is
required to act consistently, such that a < b < c.

Since your comparison function can report c < a, you are lying to the
sorter. The differences in the result are due to different implementations.

http://www.crockford.com/

 

[Thomas Mlynarczyk]

Also sprach Douglas Crockford:

Your comparison function is at fault, not the sort. The function is
required to act consistently, such that a < b < c.

But if I want to regard a and b as "equal" for sorting if their values do
not differ by more than 3? I realize now that the outcome depends on the
internal sorting algorithm implemented and that the sorting order is not
completely determined by my function. Still, I feel that sort() ought to
work the same in all browsers. There is no mentioning of this problem in any
of the documentation I have. On your website, you recommend some good books
on JavaScript - aren't there some good links as well?

 

[Fox]

Also sprach Douglas Crockford:


But if I want to regard a and b as "equal" for sorting if their values do
not differ by more than 3? I realize now that the outcome depends on the
internal sorting algorithm implemented and that the sorting order is not
completely determined by my function. Still, I feel that sort() ought to
work the same in all browsers. There is no mentioning of this problem in any
of the documentation I have. On your website, you recommend some good books
on JavaScript - aren't there some good links as well?

you're thinking mathematically -- sort functions are logical
(comparative)... [I wouldn't be surprised if some of the sort algorithms
implemented in different browsers attach significance to the magnitude
of the result -- I would -- if I were playing around]

documentation usually refers to returning the values -1, 0, or 1 and
your function is returning the result of a mathmatical expression.

try function cmp(a,b) { return a + 3 - b < 0 ? -1 : 1; }
//(0 and 1 have the same result -- 0 means a = b, order unchanged --
whereas 1 means b > a, the order also remains the same

and see if that gets you consistent results (i don't have time to test
it myself).


Fox

 

[Douglas Crockford]

Your comparison function is at fault, not the sort. The function is

But if I want to regard a and b as "equal" for sorting if their values do
not differ by more than 3? I realize now that the outcome depends on the
internal sorting algorithm implemented and that the sorting order is not
completely determined by my function. Still, I feel that sort() ought to
work the same in all browsers. There is no mentioning of this problem in any
of the documentation I have. On your website, you recommend some good books
on JavaScript - aren't there some good links as well?

Try ordering them yourself by hand with your comparison function. Then
you may get a sense of how your function is at fault. It is illogical to
expect compliant behavior when your own behavior is not compliant.

The Standard does not call for a particular sorting algorithm. Different
algorithms will examine the pairs of keys in different sequences. When
the comparison is correct (a < b, b < c, a < c) then they call have the
same result. When the comparison is wrong (a < b, b < c, a > c) then
you cannot expect the result to be stable.

Check out
http://www.ecma-international.org/publications/standards/ECMA-262.HTM
for the specification of the sort method.

 

[Lasse Reichstein Nielsen]

But if I want to regard a and b as "equal" for sorting if their values do
not differ by more than 3?

Then you should consistently return 0 when a and b are compared, no matter
in what order.

I realize now that the outcome depends on the internal sorting
algorithm implemented and that the sorting order is not completely
determined by my function. Still, I feel that sort() ought to work
the same in all browsers.

That is not required by the standard. Only the behavior for consistent
comparison functions (representing a transitive, anti-reflexive
relation[1]) is defined. In that case, the result is sorted.

There is no mentioning of this problem in any of the documentation I
have. On your website, you recommend some good books on JavaScript -
aren't there some good links as well?

The authoritative definition of ECMAScript (the standardization of
Javascript) is here:
<URL:http://www.mozilla.org/js/language/E262-3.pdf>


As a side note, both Opera and Mozilla implements the ECMAScript sort
incorrectly - they fail (almost unnoticeably) when there are empty
slots in the array
This expression should give false:
2 in ([3,,1].sort())
(IE has other errors regarding arrays, so no browser is perfect

/L

[1] I.e., for all a,b,c:
a<b & b<c => a<c (transitive)
and
a<b & b<a => b=a (antireflexive)

 

[Steve van Dongen]

Also sprach Douglas Crockford:


But if I want to regard a and b as "equal" for sorting if their values do
not differ by more than 3? I realize now that the outcome depends on the
internal sorting algorithm implemented and that the sorting order is not
completely determined by my function. Still, I feel that sort() ought to
work the same in all browsers. There is no mentioning of this problem in any
of the documentation I have. On your website, you recommend some good books
on JavaScript - aren't there some good links as well?

If you want to treat them as equal then you have to write that into
your comparison function. Still, this may work differently in various
browsers but at least it will do what you want.

function(a, b)
{
if (Math.abs(a-b)) <= 3)
return 0;
else
return a-b;
}

 

[Thomas Mlynarczyk]

Also sprach Steve van Dongen:

If you want to treat them as equal then you have to write that into
your comparison function. Still, this may work differently in various
browsers but at least it will do what you want.

function(a, b)
{
if (Math.abs(a-b)) <= 3)
return 0;
else
return a-b;
}

Thanks, but I think I have tried that version too. Without success. The
point is, as I have now realized, that - no matter how the function is
defined - the outcome will always depend on the way sort() is implemented.
If I regard two numerically different values as equal for the sorting, but
then still regard them as different in the result, the whole idea cannot
work. Thanks to you all for having helped me understand that.

 

[Thomas Mlynarczyk]

Also sprach Douglas Crockford:

Check out
http://www.ecma-international.org/publications/standards/ECMA-262.HTM
for the specification of the sort method.

Thanks for that link. I have downloaded the specification.

 

[Jim Ley]

The authoritative definition of ECMAScript (the standardization of
Javascript) is here:
<URL:http://www.mozilla.org/js/language/E262-3.pdf>

Is that URL now identical with the version available from the ECMA
themselves? IIRC it used to be different - actually more correct than
available from ECMA - who have a truly awful website.

Jim.

 

[Lasse Reichstein Nielsen]

Is that URL now identical with the version available from the ECMA
themselves? IIRC it used to be different - actually more correct than
available from ECMA - who have a truly awful website.

This link gives a document saying "Edition 3 Final" and dated 24 March 2000.
The one from ECMA says "3rd edition (December 1999)" and hasn't changed.
I have given up figuring out what the difference is, but since the one
from mozilla.org has functioning reference links, I recommend that one.

/L