Why is this sorting algorithm producing inconsistent results across browsers?

Question

I'm trying to implement a (pretty simple indeed) absolute deviation sorting algorithm in Javascript. Absolute deviation is defined as the absolute value of the difference between one element and the average of all elements. For example, given the elements 1, 4, 5 and 9, the average would be (1 + 4 + 5 + 9) / 4 = 4.75, and so the absolute deviation of each element would be calculated as follows:

• absDev(1) = |1 - 4.75| = 3.75
• absDev(4) = |4 - 4.75| = 0.75
• absDev(5) = |5 - 4.75| = 0.25
• absDev(9) = |9 - 4.75| = 4.25

Sorting the elements by ascending absolute deviance would hence give the sequence 5, 4, 1, 9. So far so good, my current Javascript implementation is giving me different results in different browsers.

Here it is: http://jsfiddle.net/WVvuu/

• In Firefox and Safari, I'm getting the expected result 5, 4, 1, 9
• In Chrome and Opera, I'm getting 4, 5, 1, 9
• In IE 10, I'm getting 1, 4, 5, 9

I guess there must be probably some very simple mistake in my code but I can't seem to find it. I'd like to understand what's wrong with it and why I'm getting a different result when I change my browser. I'd appreciate it if someone could kindly explain what I'm missing. Again, this is the code:

var array = [1, 4, 5, 9];

function absDev(x) {
    return Math.abs(x - average(array));
}

function average(array) {
    var sum = array.reduce(function(previousValue, currentValue) {
        return previousValue + currentValue;
    }, 0);
    return sum / array.length;
}

array.sort(function(x, y) {
    return absDev(x) - absDev(y);
});

alert("Sorted array: " + array);

Answer 1

I suspect it's because the state of the array while the sort is going on isn't necessarily consistent. You really shouldn't be recomputing the average on each comparison anyway:

array.sort(function(array) {
  var avg = array.reduce(function(previousValue, currentValue) {
    return previousValue + currentValue;
  }, 0);
  avg /= array.length;
  return function(x, y) {
    return Math.abs(x - avg) - Math.abs(y - avg);
  };
}(array));

See if that works better. (edit — it gives me the correct answer in Chrome.)

In more detail, my suspicion is that the sort functions where you're seeing weird results may perform swaps on the array in place, and there may be intervals during which one or more original array values is either missing or replicated while the sort mechanism is doing its thing. Thus, your averaging function sees an array (sometimes) with a different list of values, meaning that the average comes out different (sometimes).

Answer 2

The sorting function is recalculating the average of the array for every step of the sort. Different browsers may not keep the array fully intact during the sort process. You can see the effects of this if you add console.log(previousValue, currentValue); into the array.reduce function.

You need to calculate the average of the array first, and store that into a variable. Then pass that variable into the sort function. Here are the changes I made to your code:

var array = [1, 4, 5, 9];
var mean = average(array);

function absDev(x, mean) {
    return Math.abs(x - mean);
}

function average(array) {
    var sum = array.reduce(function(previousValue, currentValue) {
        console.log(previousValue, currentValue);
        return previousValue + currentValue;
    }, 0);
    return sum / array.length;
}

array.sort(function(x, y) {
    return absDev(x, mean) - absDev(y, mean);
});

console.log("Sorted array: " + array);

Answer 3

The array state while the sort is in progress is specified to be implementation defined, so you cannot trust that the items are in the array in a particular way during the sort. You must pre-calculate the average before starting the sorting process.

Reference

http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11

Quote

Perform an implementation-dependent sequence of calls to the [[Get]] , [[Put]], and [[Delete]] internal methods of obj