How does Javascript's sort() work?

Deeply Knowledge

If the result is negative a is sorted before b.

If the result is positive b is sorted before a.

If the result is 0 no changes are done with the sort order of the two values.

NOTE:

This code is the view inside of the sort method step by step.

OUTPUT:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();  //create duplicate array
var inc = 0; //inc meant increment
copy.sort((a, b) => {
 sortRes[inc] = [ a, b, a-b ];
 inc += 1;
 return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
 copy = arr.slice();
 copy.sort((a, b) => {
  p += 1;
  if (p <= i ) {
   return a - b;
  }
  else{
   return false;
  }
 });
 p = 0;
 console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

To help clarify the behavior of Array#sort and its comparator, consider this naive insertion sort taught in beginning programming courses:

const sort = arr => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && arr[j-1] > arr[j]; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);

Ignoring the choice of insertion sort as the algorithm, focus on the hardcoded comparator: arr[j-1] > arr[j]. This has two problems relevant to the discussion:

1. The > operator is invoked on pairs of array elements but many things you might want to sort such as objects don't respond to > in a reasonable way (the same would be true if we used -).
2. Even if you are working with numbers, oftentimes you want some other arrangement than the ascending sort that's been baked-in here.

We can fix these problems by adding a comparefn argument which you're familiar with:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);

sort(array, (a, b) => b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));

Now the naive sort routine is generalized. You can see exactly when this callback is invoked, answering your first set of concerns:

Is the array sort callback function called many times during the course of the sort? If so, I'd like to know which two numbers are passed into the function each time

Running the code below shows that, yes, the function is called many times and you can use console.log to see which numbers were passed in:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
  [3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);

You ask:

How are the two sets of numbers then sorted in relation to one another?

To be precise with terminology, a and b aren't sets of numbers--they're objects in the array (in your example, they're numbers).

The truth is, it doesn't matter how they're sorted because it's implementation-dependent. Had I used a different sort algorithm than insertion sort, the comparator would probably be invoked on different pairs of numbers, but at the end of the sort call, the invariant that matters to the JS programmer is that the result array is sorted according to the comparator, assuming the comparator returns values that adhere to the contract you stated (< 0 when a < b, 0 when a === b and > 0 when a > b).

In the same sense that I have the freedom to change my sort's implementation as long as I don't breach my specification, implementations of ECMAScript are free to choose the sort implementation within the confines of the language specification, so Array#sort will likely produce different comparator calls on different engines. One would not write code where the logic relies on some particular sequence of comparisons (nor should the comparator produce side effects in the first place).

For example, the V8 engine (at the time of writing) invokes Timsort when the array is larger than some precomputed number of elements and uses a binary insertion sort for small array chunks. However, it used to use quicksort which is unstable and would likely give a different sequence of arguments and calls to the comparator.

Since different sort implementations use the return value of the comparator function differently, this can lead to surprising behavior when the comparator doesn't adhere to the contract. See this thread for an example.

Is the array sort callback function called many times during the course of the sort?

Yes

If so, I'd like to know which two numbers are passed into the function each time.

a: The first element for comparison.

b: The second element for comparison.

In the following example, a will be "2" and b will be "3" in the first iteration

How are the two sets of numbers then sorted in relation to one another?

Elements are sorted according to the return value of the compare function.

greater than 0: sort a after b

less than 0: sort a before b

equal to 0: keep original order of a and b

Here is an example

var arr = [3, 2, 1, 5, 4, 6, 7, 9, 8, 10];
console.log(arr.sort((a, b) => {
  console.log(a - b, a, b);
  //b-a if sorting in decending order
  return a - b; 
}));