What is going on in this intermediate stage of Array.sort?

user_5879144 0
Viewed 215

While doing a deep dive on array methods, I decided to take a look at the steps involved in the Array.sort method. Take a look at this code to reverse the order of an array in place:

let arr = [];

for (let i = 1; i < 6; i++) {
  arr.push(i);
}

arr.sort((value1, value2) => {
  console.log(arr);
  console.log(`Comparing ${value1} : ${value2}`);
  return value2 - value1;
});

console.log(arr);

I get this output:

[1, 2, 3, 4, 5]
Comparing 1 : 2
[2, 1, 3, 4, 5]
Comparing 1 : 3
[2, 1, 1, 4, 5]
Comparing 2 : 3
[3, 2, 1, 4, 5]
Comparing 1 : 4
[3, 2, 1, 1, 5]
Comparing 2 : 4
[3, 2, 2, 1, 5]
Comparing 3 : 4
[4, 3, 2, 1, 5]
Comparing 1 : 5
[4, 3, 2, 1, 1]
Comparing 2 : 5
[4, 3, 2, 2, 1]
Comparing 3 : 5
[4, 3, 3, 2, 1]
Comparing 4 : 5
[5, 4, 3, 2, 1]

The first two steps make sense, but look at the third: [2, 1, 1, 4, 5].

Why would this be the behavior when I would expect [2, 3, 1, 4, 5]?

As you can see down the line, this repeated digit phenomenon shows up again and again until the array is finally reversed. What am I missing? It's clearly keeping a copy of the array after each mutation somewhere that isn't in arr.

arrays javascript
3 Answers

When arrays are small browsers (well...at least chrome and safari and node) use insertion sort. The behavior you are seeing is the result of looking at the array in the middle of the insertion sort loop. You can reproduce it with:

let arr = [ 1, 2, 3, 4, 5];

function InsertionSort(a, comparefn) {
    let from = 0
    let to = a.length
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element); //<-- your console.log is peaking at the array here
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element;
    }
  };

InsertionSort(arr,  (a,b) => {
    console.log(arr.join(","))
    return b-a
})
console.log(arr)

Just keep in mind that this is not a required implementation so you shouldn't necessarily count on this behavior.

user_38746230

To add to @mark-meyer answer. There is no specification for browsers on how to compare numbers based on callback provided to sort method.

For example, Array.sort() is used sometimes to uniformly randomize array with:

var shuffledArr = arr.sort(() => (Math.random() - 0.5))

In this case

If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the sort order is implementation-defined.

https://www.ecma-international.org/ecma-262/6.0/#sec-array.prototype.sort

You can check this page to see randomization results inside your browser: http://siri0n.github.io/attic/shuffle-comparison/index.html. Compare Chrome and Firefox. More than this, Firefox would choose different sorting algorithms for different field sizes. Not the answer, but I hope an interesting addition to the question.

user_47536610

Thanks for interesting question that opened a surprise.

There is side effect/consequence: if exception happened inside of comparator callback array could be broken(not just sorted partially):

let a = [1, 3, 2, 6, 4];
let stepToFail = 2;
try { 
   a.sort((x1, x2) => {
     if (!stepToFail--) throw "test"; 
     return x1 - x2;
   }); 
} catch(e) {
   // shows [1,3,3,6,4] in Chrome; data is broken and cannot be used anymore
   console.log(JSON.stringify(a)); 
}

[UPD] I reported a bug into Chromium project and it has been closed as "won't fix"

Array.prototype.sort was re-implemented in Chrome 70.0.3533. That is the reason why there is a change in behavior.

Regardless of that change, the above example does not really constitute a bug. The comparison function is not "consistent" and as per spec the resulting sort-order is implementation-defined. That includes "inconsistent state" since the exception can be thrown while looking for the right place to put a value or before it can be written back.

user_20716970
Related