How does sort function work in JavaScript, along with compare function

Question

As already asked: how does sort function work in JavaScript, along with the compare function? If I have an array, and I do array.sort(compare) now it was written in the book that if the compare function returns a-b (two indices of the array) then it works based on the fact that whether the result is greater than 0, less than 0 or equal to 0. But, how exactly does it work? I could not work it out.

Answer 1

The "compare" function must take two arguments, often referred to as a and b. Then you make the compare function return 0, greater than 0, or less than 0, based on these values, a and b.

1. Return greater than 0 if a is greater than b
2. Return 0 if a equals b
3. Return less than 0 if a is less than b

With these three return values, and only two arguments, it is possible to write a compare function that can sort any type of input data type, or complex data structures.

Then, when you call sort(), with your custom compare function, the compare function is called on pairs in your to-be-sorted list, to determine the proper ordering.

Lets walk through a simple example... Suppose you're only sorting some numbers, so we have a very simple compare function:

function compare(a,b) {     return a - b; } 

Simply subtracting b from a will always return greater than zero if a is larger than b, 0 if they are equal, or less than zero if a is less than b. So it meets the requirements for a compare function.

Now lets suppose this is our list of numbers to sort:

var numbers = [1,5,3.14]; 

When you call numbers.sort(compare), internally it will actually execute:

compare(1,5);     // Returns -4, a is less than b compare(1,3.14);  // Return -2.14, a is less than b compare(5,3.14);  // returns 1.86, a is greater than b 

If you've ever done manual sorting or alphabetizing, you've done precisely the same thing, probably without realizing it. Even though you may have dozens or hundreds of items to compare, you're constantly comparing only two numbers (or author's last names, or whatever) at a time. Going through or short list of three numbers again, you'd start by comparing the first two numbers:

1. Is 1 greater than or less than 5? Less than, so put these two numbers in our list: 1,5
2. Is 3.14 greater than or less than 1? Greater than, so it goes after 1 in the new list
3. Is 3.14 greater than or less than 5 in our new list? Less than, so it goes before 5. Our new list is now [1,3.14,5]

Because you can provide your own compare() function, it is possible to sort arbitrarily complex data, not just numbers.

Answer 2

By default, the array sort() method sorts alphabetically ascending. If you want to sort in some other order, because your array contains numbers or objects then you can pass a function in to the sort().

The function you pass in takes two parameters, often called a and b, and returns: a negative number if the first argument should be sorted before the second (a < b) 0 if the arguments are equal (a==b) a positive number if the first argument should be sorted after the second (a > b)

Now, here is the key bit: the function you pass as a parameter to sort() will be called repeatedly by sort() as it processes the whole array. sort() doesn't know or care about the datatype of the things in the array: each time it needs to know "Does item A come before item B?" it just calls your function. You don't need to worry about what type of sort algorithm is used internally by sort(), indeed one browser might use a different algorithm to another, but that's OK because you just have to provide a way for it to compare any two items from your array.

Your function could have an if / else if / else structure to decide what result to return, but for numbers simply returning (a-b) will achieve this for you because the result of the subtraction will be -ve, 0 or +ve and correctly put the numbers in ascending order. Returning (b-a) would put them descending:

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

If you had an array of objects and wanted to sort on some particular property or properties of the objects you could do that too. Assuming, e.g., objects in this format:

{ id : 1,   name : "Fred",   address : "12 Smith St",   phone : "0262626262" } 

Then you could sort an array of such objects by their 'id' attribute as follows:

var sortedArray = myArray.sort(function(a,b){                                   return (a.id - b.id);                               }); 

Or you could sort an array of such objects by their 'name' attribute (alphabetical) as follows:

var sortedArray = myArray.sort(function(a,b){                                    if (a.name < b.name)                                       return -1;                                    else if (a.name == b.name)                                       return 0;                                    else                                       return 1;                                }); 

Note that in my final example I've put the full if / else if / else structure I mentioned earlier.

For the example where you are sorting objects with multiple properties you could expand that further to include a secondary sort, that is, (in my example) if the name properties are equal you could then return a comparison of, say, the phone property.