What really happens in Javascript Sort

Question

I've seen this sort function working 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 don't really understand the mechanics of this little function. When it is comparing a and b, which numbers of the array is it really comparing? If say, it picked up the first two numbers 1 and 5, the function will return -4. What does that mean to the sort order? Or is it just the negative boolean value? Even if it is, how does the sort really happen?

Answer 1

Basically, the sort works by comparing two elements at a time. A comparison is more than a boolean--you have three options: less than, equal and greater than. 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 means a > b.

To answer the broader question: there are some relatively fast algorithms for sorting a list by comparing its elements. The most popular is Quicksort; however, Quicksort is not stable so some engines (Firefox's for sure) use a different algorithm. A simple stable sort is Mergesort.

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

Slightly random aside:

You could also imagine using a special type (like an enum) for this sort of thing. The comparing function could return LT, GT or EQ as appropriate, for example. However, in a dynamic language like JavaScript, it's much easier just to use numbers. In languages more obsessed with types (like Haskell :)), using a special order type makes more sense.