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

Question

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.

Answer 1

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.

Answer 2

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.