I don't understand WHY numerical sort functions work in Javascript

Question

I understand that the .sort() method sorts an array alphabetically, as if it was a string. Even if your array is made up entirely of numbers.

I also understand that to sort an array numerically, the code is:

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

The problem is I don't understand WHY this works. The function I wrote is supposed to take two arguments, 'a' and 'b', but where are these arguments coming from? The array? How does it know to do that? Then, the function returns some number. If 'a' and 'b' were 10 and 5, respectively, my function would be returning '5'. Now I'm doing myArray.sort(5); How the heck does that magically sort my entire array numerically???

Thanks for the help.

Answer 1

The function I wrote is supposed to take two arguments, 'a' and 'b', but where are these arguments coming from?

To determine what order array elements belong in, the Array.sort function picks pairs of elements from your array and passes them into your comparison function as a and b. The result returned by your function determines what order the two elements get placed in - if it is negative, then it knows to put a before b; if it is positive, it knows to put a after b. The actual number doesn't matter, just whether it's negative or positive.

A somewhat less confusing way of writing your example might be:

function myComparisonFunction(a, b) {
    if (a < b) {
        return -1;
    }
    if (a > b) {
        return 1;
    }
    return 0;
}

myArray.sort(myComparisonFunction);

Answer 2

The sort function operates by (cleverly) comparing pairs of array entries. Based on the result of the comparison, it knows the order for a particular pair of values. How does it know? Because it trusts the sort callback function to return

• -1 (or any negative number) if the first entry should go before the second;
• 1 (or any positive non-zero number) if the second entry should go before the first;
• 0 if the entries are the same (meaning that the order doesn't matter^*)

By repeatedly comparing pairs of array entries, and doing so systematically, the sort function eventually determines the overall correct ordering according to the inherent rules imposed by the comparator function.

The nature of the systematic process used by the JavaScript sort implementation is unspecified. It's a good bet that modern JavaScript runtimes use a fairly well-optimized quicksort.

^* when two entries in the array are equal according to the comparison function, two things might happen: the sort function may leave them in the order in which they originally appeared, or it may swap them. By the simple logic of the sort process, either of those actions are OK; if you're sorting a list of names, and "Thomas" appears twice, then it doesn't matter which "Thomas" is first and which is second since the strings are identical and indistinguishable. However, if a sort comparator function is plucking properties from pairs of objects, sometimes it does matter that entries remain in original order if their comparison returns 0. A sort function that ensures that behavior is called stable. Whether a JavaScript implementation is stable or not is undefined by the spec.

Answer 3

This comparator function, as used in Array.sort (ES5 spec., MDN), should return a number where..

• if a < b, return less than 0
• if a > b, return more than 0
• else (a == b) return 0

So, let's look at some cases:

a     b     a-b    meaning (see above)
----  ----  ----   ------
10    5     5      "a > b"
5     10    -5     "a < b"
5     5     0      "a == b" 

The comparator function defines ordering between elements which is used in a Comparison Sort algorithm:

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison [aka "comparator"]) that determines which of two elements should occur first in the final sorted list.

(Note: The sort by Array.sort is not guaranteed to be stable.)

Answer 4

Now I'm doing myArray.sort(5);

That's not true. Passing in a function that (sometimes) returns 5 is not at all the same thing as passing in 5.

What happens is, you pass in a function that sort can call whenever it needs to know which of two values should be considered greater. sort will pass two arguments to that function. If the function returns a negative value, that means "the first argument is less than the second argument"; if it returns zero, that means "the two arguments should be considered equal"; if it returns a positive value, that means "the first argument is greater than the second argument". (This might seem a bit hackish and arbitrary — and maybe it is — but it has a long history in C-like languages.) So, for numeric comparisons, it's convenient to just return a-b, since that meets these requirements.

Note that you cannot predict exactly which comparisons sort will decide to perform, so you need to make sure to pass in a function that behaves consistently. For example, if your function says that 1 is less than 2 and 2 is less than 3, then your function also needs to say that 2 is greater than 1, that 3 is greater than 2, that 1 is less than 3, and that 3 is greater than 1. Otherwise, you might get random-seeming results.

(You may be interested in the MDN page on Array.prototype.sort, by the way. It gives a number of other examples, which might help clarify this for you.)

Answer 5

So it runs through and applies whatever algorithm it wants to sort the values in your array. All it needs to know is how to tell which one is "bigger" or which one should be forward indexed.

I guess it helps to have some more familiarity with how javascript works. With javascript you can assign variables as functions and as such you can pass functions as parameters. It comes in handy in situations like this and for asynchronous callbacks (if you've played with jquery you've likely seen this in ajax calls and they're called for after various transformations are completed...like if you want one element to move 500px and then as soon as it completes it you move it down 500px, you put the down move function in the call back).

long story short, the a and b values come from your array, which values it pulls out are up to the sort function.

the awesome thing about the comparison function of sort is say you have an object that looks like this:

sales:[{sale:{"brand":"Nike", "person":"Eric", "total":5000}}, {sale:{...}}]

you can do use a sorting function to sort by brand then total like this:

sales.sort(function(a,b){
    if (a.brand==b.brand){
       return a.brand>b.brand ? 1 : -1;
    } else {
       return a.total-b.total;
});

I tend to think stuff like that is really neat...it lets the language use the most efficient sorting algorithm it feels like using and all you have to do is show it how to determine if one is "bigger" than another.

Answer 6

a and b two consecutive values in array to compare and subtraction can be 0, less than zero and greater than zero.. if greater than zero, it means prior element is larger so it needs to be pushed further down if it is less than zero, it means it needs not to be pushed down..

Answer 7

In your example, you're NOT doing myArray.sort(5);, because you pass a function (that is used to guide the sorting algorithm), not a number.