How does Javascript's sort() work?

Question

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!

Answer 1

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

Yes, that's exactly it. The callback is used to compare pairs of elements in the array as necessary to determine what order they should be in. That implementation of the comparison function is not atypical when dealing with a numeric sort. Details in the spec or on some other more readable sites.

Answer 2

The Javascript interpreter has some kind of sort algorithm built into it. It calls the comparison function some number of times to do the sort, with the number of times depending on the particular algorithm, the data to be sorted, and the order it is in prior to the sort. Some sort algorithms, for example, perform poorly on already-sorted lists because it causes them to make a lot of comparisons. Others cope well with that, 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 one most often used, as it has a good balance of properties, is Quicksort. Whether your JS interpreter uses that one or something else is an implementation detail.

EDIT: Some JS interpreters use merge sort instead. One of the nice properties of merge sort is that it is stable.

Answer 3

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(function(a,b) {

   alert( "comparing " + a + ",  " + b );
  return a - b

});

EDIT

This is the output I've got:

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

Answer 4

Pairs of values are compared, one pair at a time. The pairs that are compared are an implementation detail--don't assume they will be the same on every browser. The callback can be anything (so you can sort strings or Roman numerals or anything else where you can come up with a function that returns 1,0,-1).

One thing to keep in mind with JavaScript's sort is that it is not guaranteed to be stable. For instance, this test for stability currently fails in Chrome (mine is current at 3.0.195.24):

http://www.hedgerwow.com/360/dhtml/js%5Farray%5Fstable%5Fsort.html

Answer 5

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

Since this is a comparison sort, given N items, the callback function should be invoked on average (N * Lg N) times for a fast sort like Quicksort. If the algorithm used is something like Bubble Sort, then the callback function will be invoked on average (N * N) times.

The minimum number of invocations for a comparison sort is (N-1) and that is only to detect an already sorted list (i.e. early out in Bubble Sort if no swaps occur).