Closed Bug 1715486 Opened 3 years ago Closed 3 years ago

Array.sort is not working properly with return 0

Categories

(Core :: JavaScript: Standard Library, defect)

Firefox 89
defect

Tracking

()

RESOLVED INVALID
Tracking Status
firefox89 --- affected
firefox90 --- affected
firefox91 --- affected

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.

Same thing happens with 2 separate sort calls here: https://codepen.io/ronny25/pen/KKWBxLe

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.

Severity: -- → S4
Status: UNCONFIRMED → NEW
Component: Untriaged → JavaScript: Standard Library
Ever confirmed: true
Product: Firefox → Core

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);
});
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → INVALID

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);

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?

Flags: needinfo?(andrebargull)

(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);
}
Flags: needinfo?(andrebargull)
You need to log in before you can comment on or make changes to this bug.