How does Javascript's sort() work?

How does the following code sort this array to be in numerical order?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

I know that if the result of the computation is...

Less than 0: "a" is sorted to be a lower index than "b".
Zero: "a" and "b" are considered equal, and no sorting is performed.
Greater than 0: "b" is sorted to be a lower index than "a".

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. I assumed it first took "25"(a) and "8"(b), followed by "7"(a) and "41"(b), so:

25(a) - 8(b) = 17 (greater than zero, so sort "b" to be a lower index than "a"): 8, 25

7(a) - 41(b) = -34 (less than zero, so sort "a" to be a lower index than "b": 7, 41

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

Please help a struggling newbie!

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

You could find out your self with:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

EDIT

This is the output I've got:

25,8
25,7
8,7
25,41

The JavaScript interpreter has some kind of sort algorithm implementation built into it. It calls the comparison function some number of times during the sorting operation. The number of times the comparison function gets called depends on the particular algorithm, the data to be sorted, and the order it is in prior to the sort.

Some sort algorithms perform poorly on already-sorted lists because it causes them to make far more comparisons than in the typical case. Others cope well with pre-sorted lists, but have other cases where they can be "tricked" into performing poorly.

There are many sorting algorithms in common use because no single algorithm is perfect for all purposes. The two most often used for generic sorting are Quicksort and merge sort. Quicksort is often the faster of the two, but merge sort has some nice properties that can make it a better overall choice. Merge sort is stable, while Quicksort is not. Both algorithms are parallelizable, but the way merge sort works makes a parallel implementation more efficient, all else being equal.

Your particular JavaScript interpreter may use one of those algorithms or something else entirely. The ECMAScript standard does not specify which algorithm a conforming implementation must use. It even explicitly disavows the need for stability.

How does Javascript's sort() work?

Related

Recent Posts