Array.sort is not working properly with return 0
Categories
(Core :: JavaScript: Standard Library, defect)
Tracking
()
People
(Reporter: kotkin.lg, Unassigned)
Details
User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:89.0) Gecko/20100101 Firefox/89.0
Steps to reproduce:
Sort is not stable compared to other browsers like Chorme or Safari - it doesn't give back the predicted result.
I've created a small codepen example of the issue: https://codepen.io/ronny25/pen/jOBpvbm?editors=0010
P.S. check the console logs.
Actual results:
DE item is sorted alphabetically.
Expected results:
DE item of the array has to be first in the list after sorting applied but it's not.
Reporter | ||
Comment 1•3 years ago
|
||
Same thing happens with 2 separate sort calls here: https://codepen.io/ronny25/pen/KKWBxLe
Comment 2•3 years ago
|
||
Reproduced on the latest versions of Firefox 91.0a1 (2021-06-10), beta 90.0b5 and release 89.0.
Setting up flags, a severity of S4 and a component for this issue in order to get the dev team involved.
If you feel it's an incorrect one please feel free to change it to a more appropriate one.
Not a recent regression since it can be traced back to at least Firefox 70.0.
Comment 3•3 years ago
|
||
The function passed to Array.prototype.sort
isn't a "consistent comparison function", therefore you don't get the expected result. If you use this comparison function, you should get the expected result.
array.sort((prev, next) => {
if (prev.value === next.value) {
return 0;
}
if (prev.value === tenant) {
return -1;
}
if (next.value === tenant) {
return 1;
}
return prev.name.localeCompare(next.name);
});
Comment 4•3 years ago
|
||
Here's an example to show that all browsers use different sort algorithms and therefore will return different results when the comparison function doesn't return consistent results.
// Array with ascending values from 0 to 999, every 10th value is 100.
//
// The array is large enough to ensure browsers don't just use insertion sort
// in their Array.prototype.sort implementation.
var a = Array.from({length: 1000}, (x, i) => i % 10 !== 0 ? i : 100);
// This function is not a consistent comparison function.
a.sort((x, y) => {
if (x === 100) {
return -1;
}
return x - y;
});
// Each browser (Firefox, Safari, Chrome) should print a different array here.
console.log(a);
Reporter | ||
Comment 5•3 years ago
|
||
Why then second example also doesn't work?
Is it also considered as not consistent? Why only for Firefox?
And where can I get more information on what is defined as "consistent" function?
Comment 6•3 years ago
|
||
(In reply to Dmytro Kotkin from comment #5)
Why then second example also doesn't work?
Is it also considered as not consistent? Why only for Firefox?
The different results are a side-effect of in which order the elements are passed to the comparison function. For example here is the source code of the insertion sort algorithm Firefox is using. The relevant line is:
if (comparefn(swap, item) <= 0)
If the line was changed to:
if (comparefn(item, swap) > 0)
Your comparison would suddenly work correctly, even though it's still not a consistent comparison function.
And where can I get more information on what is defined as "consistent" function?
When you follow the link in comment #3, you get to the specification of Array.prototype.sort
, which includes the definition of consistent comparison functions.
For example for the first comparison function:
var compare = (prev, next) => {
if (prev.value === tenant) {
return -1;
}
return prev.name.localeCompare(next.name);
}
When called with compare({value: 'DE', name: 'Germany'}, {value: 'BE', name: 'Belgium'})
it returns -1
. But it also returns -1
when called with compare({value: 'BE', name: 'Belgium'}, {value: 'DE', name: 'Germany'})
, i.e. both parameters are swapped. This is obviously not correct, because the second call should return 1
. Therefore the comparison function needs to be changed to:
var compare = (prev, next) => {
if (prev.value === tenant) {
return -1;
}
if (next.value === tenant) {
return 1;
}
return prev.name.localeCompare(next.name);
}
But there's still the issue that compare({value: 'DE', name: 'Germany'}, {value: 'DE', name: 'Germany'})
returns -1
, whereas for consistent comparison functions we're required to return 0
, because both elements should be considered equal to each other. To fix this last issue, another if
-statement to handle the case prev.value === next.value
needs to be added.
var compare = (prev, next) => {
if (prev.value === next.value) {
return 0;
}
if (prev.value === tenant) {
return -1;
}
if (next.value === tenant) {
return 1;
}
return prev.name.localeCompare(next.name);
}
If you also want to handle the case when two elements have the same value
property, but a different name
property, the comparison function actually needs to be:
var compare = (prev, next) => {
if (prev.value !== next.value) {
if (prev.value === tenant) {
return -1;
}
if (next.value === tenant) {
return 1;
}
}
return prev.name.localeCompare(next.name);
}
Description
•