CODEWITHSUNDEEP
javascriptgoogle-chromefirefox
Martin Honnen
Martin Honnen

Reputation: 167461

Different result with Array.sort(comparisonFunction) in Chrome and Firefox

I am using anArrayOfObjects.sort((a, b) => a.value - b.value), where some objects don't have a value property.

That leads to different results in Firefox and Chrome, where Chrome seems to sort the object(s) with no value property/undefined value to the end, Firefox doesn't.

Is the spec not prescribing the result that Chrome gives, meaning the Firefox result is wrong? Or is that part of the sort result up to a particular implementation?

const data2 = [
  { 'name' : 'a', 'value' : 5 },
  { 'name' : 'b', 'value' : 2 },
  { 'name' : 'c' },
  { 'name' : 'd', 'value' : 1 }
];

console.log('before sorting: ', data2);

data2.sort((a, b) => a.value - b.value);

console.log('after sorting: ', data2);

Upvotes: 4

Views: 772

Answers (4)

n--
n--

Reputation: 3856

It is widely known that sorting algorithms are browsers implementation specific, moreover, since there are no silver bullet algorithms, a certain browser may use different sorting algorithms for different data shapes as a optimization technique.
This became obvious when looking at the following example results in Firefox:

const arr1 = [
  { 'value' : 5 },
  { 'value' : 2 },
  { 'value': undefined },
  { 'value' : 4 },
  { 'value' : 3 },
  { 'value': undefined },
  { 'value' : 1 },
  { 'value' : 0 }
];

const arr2 = [5, 2, undefined, 4, 3, undefined, 1, 0];

arr1.sort((a, b) => a.value - b.value);

arr2.sort((a, b) => a - b);

console.log(arr1.map(v => `${v.value}`).join());

console.log(arr2.map(v => `${v}`).join());

In fact, Chrome results for the above examples are compliant with the specs:

  1. Let SortCompare be a new Abstract Closure with parameters (x, y) that captures comparefn and performs the following steps when called:
    a. If x and y are both undefined, return +0𝔽.
    b. If x is undefined, return 1𝔽.
    c. If y is undefined, return -1𝔽.

From the above statement can be concluded that undefined values always compares greater than any other value, that's why they are sorted at the end.
This result can be achieved with a merge sort algorithm with special handling of undefined values, below is a pseudo-code of this:

const mergeSort = arr => {
    let voids = 0;
    const merge = (l, r) => {
        const out = [];
        l.length && l[0] === undefined && (l.shift(), voids++);
        while (l.length && r.length) out.push(l[0] <= r[0] ? l.shift() : r.shift());
        while(l.length) out.push(l.shift());
        while(r.length) out.push(r.shift());
        return out;
    };
    const sort = arr => {
        if (arr.length < 2)
            return arr;
        const m = Math.floor(arr.length / 2);
        const l = arr.slice(0, m), r = arr.slice(m);
        return merge(sort(l), sort(r));
    };
    const result = sort(arr);
    while (voids--) result.push(undefined);
    return result;
};

const arr = [5, 2, undefined, 4, 3, undefined, 1, 0];

console.log(mergeSort(arr).map(v => `${v}`).join());

About the sorted array of objects result in Firefox, in the first example, it can be obtained with a simple insertion sort algorithm, as below:

const insertionSort = arr => {
    for (let i = 1; i < arr.length; i++) {
        let x = i - 1, n = arr[i];
        for (; x >= 0 && arr[x] > n; x--)
            arr[x + 1] = arr[x];
        arr[x + 1] = n;
    }
    return arr;
};

const arr = [5, 2, undefined, 4, 3, undefined, 1, 0];

console.log(insertionSort(arr).map(v => `${v}`).join());

Upvotes: 0

jonrsharpe
jonrsharpe

Reputation: 121975

The compare function works as follows:

compareFn(a, b) return value sort order
< 0 sort a after b
> 0 sort a before b
=== 0 keep original order of a and b

Any subtractions involving undefined give a return value of NaN, which per the spec, is immediately converted to 0. However, the order will depend on the specific algorithm used by the implementation, as that determines which values get compared in this way.

The issue becomes clearer when you log out the comparisons:

const data2 = [
  { 'name' : 'a', 'value' : 5 },
  { 'name' : 'b', 'value' : 2 },
  { 'name' : 'c' },
  { 'name' : 'd', 'value' : 1 }
];

console.log('before sorting: ', data2);

data2.sort((a, b) => (console.log(a.value, b.value), a.value - b.value));

console.log('after sorting: ', data2);

  • Firefox seems to be asking > 0:

    5 2
5 undefined
undefined 1
    1. a is 'a' and b is 'b', return value is 3 so 'a' is must be after 'b'.
    2. a is 'a' and b is 'c', return value is 0 so 'a' stays before 'c'.
    3. a is 'c' and b is 'd', return value is 0 so 'c' stays before 'd'.

  • Chrome seems to be asking < 0:

    2 5
undefined 2
undefined 5
1 5
1 2
    1. a is 'b' and b is 'a', return value is -3 so 'b' must be before 'a'.
    2. a is 'c' and b is 'b', return value is 0 so 'c' stays after 'b'
    3. a is 'c' and b is 'a', return value is 0 so 'c' stays after 'a'
    4. a is 'd' and b is 'a', return value is -4 so 'd' must be before 'a'
    5. a is 'd' and b is 'b', return value is -1 so 'd' must be before 'b'

Specifically Chrome doesn't ever compare 'c' and 'd' directly, so is never told to keep them in the same order.

Upvotes: 0

Cerbrus
Cerbrus

Reputation: 72837

Neither are "wrong".

undefined - undefined, undefined - 1 and 1 - undefined all return NaN, and NaN compared to something is always false.

The difference between the 2 browsers is probably due to sorting implementation.
The used sorting algorithm can give different results, depending on the order of values beforehand, and how the implementation deals with NaN.

Upvotes: 3

Volodymyr Sichka
Volodymyr Sichka

Reputation: 561

Don't allow browsers engines to decide how to handle your code in doubtful situations, just write your code without it:

data2.sort((a, b) => (a?.value || 0) - (b?.value || 0));

(Default value could be some small or big number to sort with order you need.)

Upvotes: 1

Related Questions