QuestionCactus QuestionCactus - 4 months ago 7
Javascript Question

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

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.

Answer

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

Comments