Why is the Array.sort() method in my Javascript program unstable?

Question

Here is my jsFiddle:

//Change this variable to change the number of players sorted
var numberOfPlayers = 15;

var teams = [];
var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

for(var a=0; a<numberOfPlayers; a++){
  updateStandings();
    teams.push(new Team(alphabet.charAt(a)));
}

console.log("Teams:");
for(var x=0; x<teams.length; x++){
    console.log(teams[x].name);
}

//Functions and such
function updateStandings(){
  teams.sort(function(a, b) { 
    if(a.score == b.score){ 
      if(a.tiebreak == b.tiebreak){
        return teams.indexOf(a)-teams.indexOf(b);
      }else{
        return b.tiebreak-a.tiebreak;
      }
    }else{
      return b.score-a.score;
    }
  });
}

function Team(name){
  this.name = name;
  this.score = 0;
  this.tiebreak = 0;
}

I assumed the problem was that javascript sorting was unstable, and changed my compare function, but it still does not work.

Since `tiebreak` is always 0, it will do nothing. I don't think you need `tiebreak` at all. Just return the difference in indexes. — , Jul 18 '16 at 19:50
@PatrickEvans Perhaps I was unclear. My issue is that the sorting algorithm is unstable and I cannot make it stable. Have you tested the jsFiddle? — QuestionCactus, Jul 18 '16 at 19:51
@torazaburo Perhaps I was unclear. My issue is that the sorting algorithm is unstable and I cannot make it stable. Have you tested the jsFiddle? — QuestionCactus, Jul 18 '16 at 19:51
A fiddle is code on jsfiddle, please post it there if you want people to play with it. However a fiddle is not necessary to find basic problems in code. In your case, since `tiebreak` is always 0, it will do nothing, as I said. — , Jul 18 '16 at 19:52
What exactly is your problem? What does not work? What happens when you run the code, and what would you have expected instead? — Bergi, Jul 18 '16 at 19:56
@Bergi Sure, his question is poorly formed, and the sample code won't work well to prove anything, but surely the question of how to ensure stable sorting in JS, which is what this question boils down to, is interesting and does not need more elaboration (but might well be a duplicate). — , Jul 18 '16 at 20:29
See also http://stackoverflow.com/questions/3026281/array-sort-sorting-stability-in-different-browsers. One of the answers there describes the notion of sorting an array of indices, which is what I do in my answer below. — , Jul 18 '16 at 20:30

score 2 · Answer 1 · edited May 23 '17 at 11:51

The generic approach to stable sorting in JS is as follows:

function stable_sort(array, sortfunc) {
  function _sortfunc(a, b) { return sortfunc(array[a], array[b]) || a - b; }

  return array.map((e, i) => i) . sort(_sortfunc) . map(i => array[i]);
}

What this actually does is to sort a list of indices. Then it maps the sorted list of indices back to the original array. The sort function is rewritten to compare the values in the array at those indices, and if they are equal then fall back to a comparison of indices themselves.

This approach avoids the problem in your code which is that it is doing indexOf look-ups into an array which is the middle of being sorted.

This question could be informative.

score 1 · Answer 2 · answered Jul 18 '16 at 20:04

According to the documentation, sort method is not required to be stable: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort In some browsers it is stable, in some not.

You do need to change the compare function, but not in the way that you tried. The reason is that you compare

return teams.indexOf(a)-teams.indexOf(b);

in the current array. It means that if the order of a and b has changed on the previous steps, your sorting routine will preserve this new order, not the one that these elements had in the beginning.

There are different ways to solve it. For example, you can create a copy of the array before sorting and execute indexOf on this copy. It will preserve the order that elements had had before sorting started.

But if your know that order in advance, you can also use this knowledge. For example, if before sorting the teams was sorted by their names, you can compare names as strings instead of positions in the array, it would be much more efficient than the first option.

ssube · Accepted Answer · 2016-07-18T20:02:37.997

0

Because JS' sorting is typically unstable. From §22.1.3.24 of the spec:

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

Your teams are created with identical properties except their name, so the line actually performing the sort is:

return teams.indexOf(a)-teams.indexOf(b);

Because you're calling indexOf, it searches for the item (and its index) each repetition of the sort. Sorting mutates the array (from MDN: it "sorts the elements of an array in place and returns the array").

You are searching for the item within the same array you are sorting, so the index may change on each iteration. Done correctly (relatively speaking), you could produce a never-ending sort with that.

For example:

const data = [1, 3, 2, 4];
let reps = 0;

data.sort((a, b) => {
  console.log(data);
  
  const ia = data.indexOf(a), ib = data.indexOf(b);
  if (ia === ib || reps > 50) {
    return 0;
  } else if (ia < ib) {
    return 1;
  } else if (ib < ia) {
    return -1;
  }    
});

edited Jul 18 '16 at 20:02

answered Jul 18 '16 at 19:53

ssube

47,010
7
103
140

I feel stupid. Of course sorting mutates the array. How would you go about solving the problem? Would you create your own sorting method or try a workaround like I did? – QuestionCactus Jul 18 '16 at 19:54
@torazaburo as my example shows, the mutation occurs while the sort is still in progress. This can thoroughly break your sorting function if you're accessing the array as you go. – ssube Jul 18 '16 at 19:59
@QuestionCactus you have a few options: use a sorting algorithm that does not depend on the previous position (probably the best idea) or make a shallow copy and sort that (using position from the original). – ssube Jul 18 '16 at 20:00
Yeah, I guess I'll just create my own sorting method using Merge Sort or something. Thanks. – QuestionCactus Jul 18 '16 at 20:02
I would suggest making the smallest change you can. Either `[].concat(data)` to make a copy or tweak your sort so it doesn't need the previous position. – ssube Jul 18 '16 at 20:03
Hmm . . . this also doesn't work - https://jsfiddle.net/QuestionCactus/61ho6oqh/ – QuestionCactus Jul 18 '16 at 20:12
*Because JS' sorting is typically unstable.* This doesn't answer the question. We all know that JS sorting is unstable (sometimes). The OP's question is "Why does my attempt to make a stable sort fail?". You identified the problem with `indexOf`, but a full answer should provide an actual solution. – Jul 18 '16 at 20:33
ECMAScript 2019 mandates that `Array.prototype.sort` is stable. – Sebastian Simon Aug 24 '21 at 21:14

Why is the Array.sort() method in my Javascript program unstable?

3 Answers3