Javascript sorting function incorrectly changes elements' position in array

Question

I'm using an array sorting function with my AngularJS app. It uses a variable, direction, to determine whether to sort the data in an ascending (direction === -1) or descending (direction === 1) manner.

What's going wrong: Sometimes when I do a sort, elements in the array which should be in the same position are returned in a different position, without anything in the array actually changing.

For instance, if I have:

   var arr = [
       {id: 3, name: 'd'},
       {id: 2, name: 'b'},
       {id: 1, name: 'a'},
       {id: 2, name: 'c'}
   ];

and I sort it by "id" with a direction of -1, it will return with names as "a,b,c,d" as you'd expect. Then I'll sort again (changing the direction to 1) and it will reverse the direction. But then if I sort it again (with direction === -1), it will return with an order of "a,c,b,d".

This is a simplified example; in reality it's far less predictable than this.

I have a feeling I'm not using the direction properly in my sort. See below:

this.sortData = function (data, type, direction) {

    return data.sort(sortFunct);

    function sortFunct(a, b) {
        var numberTypes = ['Thread', 'Job', 'FolderCount', 'MessageCount', 'EmailCount', 'CalendarCount', 'TaskCount', 'OtherCount', 'JobId', 'BatchId', 'ItemsTotal', 'ItemsRemaining', 'ItemsFailed', 'Size', 'progress', 'PercentComplete'];
        var stringTypes = ['Level', 'StatusMessage', 'Author', 'ItemStatus', 'JobStatus', 'SourceMailbox', 'TargetMailbox', 'Subject', 'Folder', 'MessageClass', 'StatusMessage', 'Path', 'Owner1',];

        if (numberTypes.indexOf(type) !== -1) {
            return direction * (a[type] - b[type]);
        } else if (stringTypes.indexOf(type) !== -1) {
            if (!a[type]) {
                return 1;
            } else if (!b[type]) {
                return -1;
            } else {
                return a[type].localeCompare(b[type]) * direction;
            }
        } else if (type === 'DiscoveryDate' || type === 'ReceivedDate' || type === 'Timestamp') {
            if (a[type] > b[type]) {
                return direction * 1;
            } else if (a[type] < b[type]) {
                return direction * -1;
            } else {
                return 0;
            }
        } else {
            return direction * (a[type] - b[type]);
        }
    } // End sortFunct
};

Answer 1

The ECMAScript spec for .sort() does not require it to be stable, thus elements that your custom sort function says are the same (e.g. returns 0) will be in no guaranteed order with respect to each other and, in fact, the order they end up in may be influenced by the order they were in before the sort.

If you want a consistent sort, then you need to never return 0 from your custom sort function unless the two items are completely identical such that you could never tell which was which.

When the primary key is the same, you need to then test a secondary key and return the result of that comparison. If the secondary key is the same, then compare a tertiary key and so on as far as it is worth it to you to go.

This secondary comparison can make the sort stable so that it will always land in a predictable order, no matter what order you had it in before.

---

I've also seen sort schemes that create a unique key and assign it to every object and use that as the secondary or tertiary key, thus guaranteeing that if the keys you care about are the same, you can then compare the unique key and always have a consistent stable sort.

---

Here's an example of a scheme that preserves the original order if the comparison field (age in this case has the same value). To know what the original order was, it tags each object with an origOrder property that identifies the original order.

var data = [
  {name: "Amy", age: 13},
  {name: "Anne", age: 13},
  {name: "John", age: 11},
  {name: "Jack", age: 12},
  {name: "Ted", age: 11},
  {name: "Alice", age: 12}
];
  
// mark each object with the original order  
data.forEach(function(item, index) {
  item.origOrder = index;
});  
  
data.sort(function(a, b) {
  var diff = a.age - b.age;
  if (diff !== 0) {
    return diff;
  } else {
    return a.origOrder - b.origOrder;
  }
});  

// show results in snippet
document.write(JSON.stringify(data));  

Using a Map object from ES6, we could also do this without touching the original objects in the array by creating a temporary index that we used for resolving ties and storing that in the Map object. That could work like this:

    var data = [
      {name: "Amy", age: 13},
      {name: "Anne", age: 13},
      {name: "John", age: 11},
      {name: "Jack", age: 12},
      {name: "Ted", age: 11},
      {name: "Alice", age: 12}
    ];
    
    // put each object in a temporary map with its original index
    let tempMap = new Map();
    data.forEach((item, index) => {
        tempMap.set(item, index);
    });
      
    data.sort(function(a, b) {
      var diff = a.age - b.age;
      if (diff !== 0) {
        return diff;
      } else {
        return tempMap.get(a) - tempMap.get(b);
      }
    });  

    // show results in snippet
    document.write(JSON.stringify(data));  

You can see, by looking at the sorted results, that the relative order of two entries with the same age is retained without modifying the original objects in any way.

Answer 2

"The sort() method sorts the elements of an array in place and returns the array. The sort is not necessarily stable."

See:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

And also:

https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

'HTH,

Answer 3

ECMAScript does not require the sort to be stable (related question). Also, even if the sort is stable, you can't expect the code to know when identical records (2 and 2) should be reversed and when not. In order to be able to do this, you cannot afford to ever return 0 from the comparator - i.e. in case of a tie, you need a secondary key that will help disambiguate the order. If you can't think of anything better, you can give each object a unique ID.