What Really Happens in Javascript Sort

Question

I saw how this sorting function works fine:

var arr = [1,5,3,7,8,6,4,3,2,3,3,4,5,56,7,8,8]; console.log(arr.sort( function(a,b) { return a - b; } )); 

But I do not really understand the mechanics of this small function. When it compares a and b , what numbers in the array does it really compare? If, say, he took the first two numbers 1 and 5 , the function will return -4 . What does this mean for sort order? Or is it just a negative boolean? Even if this is so, how is this really happening?

Answer 1

Basically, sorting works by comparing two elements at a time. The comparison is more than logical - you have three options: less, equal, and more. In JavaScript, these three values ​​are represented by n <0, 0, and n> 0, respectively.

In other words, negative numbers mean a < b ; 0 means a = b and positive values a > b .

To answer a broader question: there are several relatively fast algorithms for sorting a list by comparing its elements. The most popular is Quicksort ; however, Quicksort is unstable, so some engines (Firefox for sure) use a different algorithm. Simple stable view of Mergesort .

Sorting algorithms are often one of the first algorithms analyzed in intro CS classes, because they are simple, but still interesting and non-trivial, to illustrate how to analyze the algorithms in general. You should read about them for this reason and simply because they are pretty cool.

Slightly random aside:

You could also imagine using a special type (such as an enumeration) for this kind of thing. For example, a comparison function may return LT , GT or EQ , if necessary. However, in a dynamic language such as JavaScript, it is much easier to use numbers. In languages ​​more obsessed with types (like Haskell :)), using a special order type makes more sense.

Answer 2

You have 3 options minus (-), equal (==) and plus (+):

• minus : if a - b < 0 , then a to b
• equals : doesn't matter
• plus : if a - b > 0 , then b to a

See this topic for more information: Implementing Javascript Array.sort?

Answer 3

When passing the Array.sort function, it will be used to compare a and b . How they will be sorted depends on what the function returns:

• If result < 0 , then a preceded by b ;
• If result == 0 , then a and b already in the correct order;
• If result > 0 , then a appears after b .

If sort is called without an argument, the elements are converted to strings and compared alphabetically.

By the way, the sort algorithm used is completely dependent on the browser implementation. This could be a quick sort, merge sort, or something else. The ECMAScript standard does not specify any requirements in this regard.