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?

Tikhon Jelvis · Accepted Answer · 2011-12-21T11:26:12.560

7

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.

edited Dec 21 '11 at 11:26

answered Dec 21 '11 at 11:18

Tikhon Jelvis

67,485
18
177
214

Okay, gone through the Mergesort Wikipedia entry and it makes sense (broadly). But if I wanted to take a look at how the sort function implementation has been written in Javascript, how can I? – Adnan Khan Dec 21 '11 at 11:42
@Capex - Javascript doesn't use any one sort algorithm, that is, there's no specification that says "must use bubble sort" or whatever. Different Javascript implementations (in different browsers) may use different sort algorithms. But the array sort method with the a and b parameters will still be the same to Javascript programmers because it simply provides a way for the underlying algorithm to compare any two given values. – nnnnnn Dec 21 '11 at 11:55
1

I think the issue here is that the built-in sort function is probably *not* written in JavaScript--I suspect most engines implement it in native code for performance reasons. You can see webkit's sort [here](http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp) if you scroll down a bit. If you just want any sorting algorithm in JavaScript, [here](http://en.literateprograms.org/Merge_sort_(JavaScript))'s a literate one that has plenty of commentary. – Tikhon Jelvis Dec 21 '11 at 11:55

score 1 · Answer 2 · edited May 23 '17 at 11:51

1

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

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

See this thread for more information: Javascript Array.sort implementation?

edited May 23 '17 at 11:51

Community

1
1

answered Dec 21 '11 at 11:17

Niels

48,601
4
62
81

score 1 · Answer 3 · answered Dec 21 '11 at 11:24

When passing a function to Array.sort, 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 comes before b;
If result == 0, then a and b are already in the right order;
If result > 0, then a comes after b.

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

By the way, which algorithm sort uses depends entirely on the browser's implementation. It could be quick sort, merge sort, or anything else. The ECMAScript standard doesn't specify any requirements in this regard.

What really happens in Javascript Sort

3 Answers3

Linked