Sort array items and preserve order of same elements

Question

Suppose I have this array:

var array = [
  { name: "border-color", value: "#CCCCCC" },
  { name: "color", value: "#FFFFFF" },
  { name: "background-color", value: "rgb(0, 0, 0)" },
  { name: "background-color", value: "rgba(0, 0, 0, .5)" }
];

And this function to sort the array by name:

array.sort(function(a, b) {
  if (a.name < b.name) return -1;
  if (a.name > b.name) return 1;
  return 0;
});

And ECMAScript language specifications that tell me that:

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order).

So, after sorting, the two items with name = background color could appear in any order i.e.:

[
  { name: "background-color", value: "rgb(0, 0, 0)" },
  { name: "background-color", value: "rgba(0, 0, 0, .5)" },
  ...
]

Or

[
  { name: "background-color", value: "rgba(0, 0, 0, .5)" },
  { name: "background-color", value: "rgb(0, 0, 0)" },
  ...
]

How can I sort the array so that items with same name maintain their relative order? I would rather not hardcode anything.

Check out this answer for short ES6 implementation of stable sort: https://stackoverflow.com/a/48660568/1260020 — simo, Feb 07 '18 at 09:52

noveyak · Answer 1 · 2015-07-03T21:00:04.537

38

Theoretically before sorting you could keep track of its index in the array and take that into account when sorting.

var sortArray = yourarray.map(function(data, idx){
    return {idx:idx, data:data}
})

sortArray.sort(function(a, b) {
  if (a.data.name < b.data.name) return -1;
  if (a.data.name > b.data.name) return 1;
  return a.idx - b.idx
});

var answer = sortArray.map(function(val){
    return val.data
});

edited Jul 03 '15 at 21:00

answered Jul 03 '15 at 20:24

noveyak

3,240
1
19
19

4

where do you get `idx` from? – Nina Scholz Jul 03 '15 at 20:38
1

Good catch, fixed the name of the arguments on the map function – noveyak Jul 03 '15 at 21:00
@noveyak Since the array contains reference type objet, the index of the element can be determined in the sort function. So we avoid the map before and after the sort. – Psddp Jul 06 '17 at 21:56

T.J. Crowder · Accepted Answer · 2022-02-11T17:56:10.690

This changed as of ES2019, Array#sort is stable, meaning that the two entries with the same name will have the same position relative to one another as they did before the array was sorted:

22.1.3.27 Array.prototype.sort ( comparefn )

The elements of this array are sorted. The sort must be stable (that is, elements that compare equal must remain in their original order).

(my emphasis)

So in your case, the order of { name: "background-color", value: "rgb(0, 0, 0)" } and { name: "background-color", value: "rgba(0, 0, 0, .5)" } will remain the same, because they compare as equal.

Prior to ES2019, the sort wasn't required to be stable, so they could have had their order reversed — or not, depending on the implementation.

Stable sort is broadly supported (not least because most engines already implemented a stable sort, so there was nothing for them to do).

Browser support table for stable sorting: https://caniuse.com/mdn-javascript_builtins_array_sort_stable — JoshuaCWebDeveloper, Feb 11 '22 at 17:54

Emad Y · Answer 3 · 2015-07-03T20:28:34.917

Add an extra attribute to the array: order

var array = [
    { name: "border-color", value: "#CCCCCC", order: 1 },
    { name: "color", value: "#FFFFFF", order: 2 },
    { name: "background-color", value: "rgb(0, 0, 0)", order: 3 },
    { name: "background-color", value: "rgba(0, 0, 0, .5)", order: 4 }
];

and then change the sort function to sort on order if the name is equal:

array.sort(function(a, b) {
    if (a.name < b.name) return -1;
    if (a.name > b.name) return 1;
    if (a.name == b.name) {
        if(a.order > b.order) return -1; else return 1;
    }
});

Note that the sign of the return for the order has to be tweaked depending on whether you want it sorted increasing or decreasing (here, I assumed you're sorting from largest to smallest, so return the one with the smaller order).

Using `else` is not needed, after a return statement. You can just do `if(a.order > b.order) return -1; return 1;` . You can also remove the wrapping `if(a.name==b.name){}` statement, which will always be true when executed (because it is neither `>` or `<`). — blex, Jul 03 '15 at 20:38

score 1 · Answer 4 · answered Aug 04 '19 at 21:37

In ES6, if you cannot guarantee the sort order because of the browser environment or transpiler plugin set-up (in an ideal world, this shouldn't be a problem), a very idiomatic/quick approach could be:

values
 .map((v, i) => ([v,i]))
 .sort(([v1,i1], [v2,i2])=> (
     (v1==v2) ? (i2-i1) : (v2-v1)
)).map(([v,i])=>v); // or above flipped

The downside of this is it isn't quite as efficient as a merge sort, but it's pretty close since most browser implementations use it for Array.prototype.sort internally or even more optimal (and in this case should end up just being about O(2n) + O(nlogn)).

The upside is it's very convenient and easy to read -- imho

score 0 · Answer 5 · answered Jul 06 '17 at 21:58

0

Since the array contains reference type objet, the index of the element can be determined in the sort function. So we avoid the map before and after the sort.

sortArray.sort((function(a, b) {
  if (a.name < b.name) return -1;
  if (a.name > b.name) return 1;
  return this.indexOf(a) - this.indexOf(b);
}).bind(sortArray));

answered Jul 06 '17 at 21:58

Psddp

998
10
17

1

Wouldn't this be slow since it has to find the index every time? – Vic Dec 12 '17 at 16:53
3

sorry down-voted: this wouldn't be ok because this.indexOf(a) and this.indexOf(b) would change while sorting. You need to memorize the initial indexes before sorting – ionescho Aug 08 '18 at 14:51
Adding with @ionescho, you will also have the wrong index returned by indexOf function, when you have multiple items with the same value in the array. – Tᴀʀᴇǫ Mᴀʜᴍᴏᴏᴅ Feb 18 '20 at 16:19

Sort array items and preserve order of same elements

5 Answers5

Linked

Related