Chrome stable sort function

Question

I am trying to get Chrome's Array.sort() function to be stable. I know there are other libraries that implements a stable sort, but I am trying to get the native Array.sort() to be stable as I am using some other library that listen to the sort() function to trigger animation, but it's getting wonky on Chrome as it's not stable.

 myArray.sort(function (a, b) {
    if (a.someVal > b.someVal) return -1
    else if (a.someVal < b.someVal) return 1
    //return 0  I shouldn't return 0 as its order will be randomise by chrome

    // My hack around idea was to somehow track their index but this is not working, probably while sorting is ongoing, looking up the index gets messed up? IDK.
     let aIndex = myArray.findIndex(x => x.id === a.id)
     let bIndex = myArray.findIndex(x => x.id === b.id)
     return aIndex < bIndex ? -1 : 1
  })

Anyone has any idea how to get chrome's sort function to be stable?

Example, lets sort by b, decreasing. Given

[
{'a':1,'b':1},
{'a':2,'b':1},
{'a':3,'b':1},
{'a':4,'b':1},
{'a':5,'b':1},
{'a':6,'b':1},
{'a':7,'b':2},
]

Expected stable sort

[
{'a':7,'b':2},
{'a':1,'b':1},
{'a':2,'b':1},
{'a':3,'b':1},
{'a':4,'b':1},
{'a':5,'b':1},
{'a':6,'b':1}
]

Chrome's unstable sort

[
{'a':7,'b':2},
{'a':4,'b':1},
{'a':3,'b':1},
{'a':2,'b':1},
{'a':1,'b':1},
{'a':6,'b':1},
{'a':5,'b':1}
]

Possible duplicate of [Fast stable sorting algorithm implementation in javascript](https://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript) — sapics, Nov 10 '17 at 06:07
@JonasW. Returning 0 will leave the the fate of ordering to the browser, which may not be stable as with the case of Chrome. — Gavin, Nov 10 '17 at 07:31

score 2 · Answer 1 · answered Nov 10 '17 at 06:20

Get an array that includes indexes first:

const withIndexes = myArray.map(
    (x, i) => ({index: i, value: x}));

Make a function to sort on multiple comparisons:

const compareAll = (...comparisons) => (a, b) =>
    comparisons.reduce((m, f) => m || f(a, b), 0);

May as well make another function to compare some values with </>:

const compareDefault = (a, b) =>
    a < b ? -1 :
    a > b ? 1 :
    0;

Sort by value, then by index:

withIndexes.sort(compareAll(
    (a, b) => -compareDefault(a.value.someVal, b.value.someVal),
    (a, b) => compareDefault(a.index, b.index),
));

Get just the values again:

const sorted = withIndexes.map(x => x.value);

With your example:

const compareAll = (...comparisons) => (a, b) =>
    comparisons.reduce((m, f) => m || f(a, b), 0);

const compareDefault = (a, b) =>
    a < b ? -1 :
    a > b ? 1 :
    0;

const myArray = [
    {'a':1,'b':1},
    {'a':2,'b':1},
    {'a':3,'b':1},
    {'a':4,'b':1},
    {'a':5,'b':1},
    {'a':6,'b':1},
    {'a':7,'b':2},
];

const withIndexes = myArray.map(
    (x, i) => ({index: i, value: x}));

withIndexes.sort(compareAll(
    (a, b) => -compareDefault(a.value.b, b.value.b),
    (a, b) => compareDefault(a.index, b.index),
));

const sorted = withIndexes.map(x => x.value);

console.log(sorted);

This was what I did. Figured that the behaviour of finding the index whilst sorting is taking place is probably undefined. I just need to prepare the indices beforehand like what you did. — Gavin, Nov 10 '17 at 07:10

Chrome stable sort function

1 Answers1