How Does Sort Function Work in JavaScript, Along with Compare Function

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

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.

How does the JavaScript sort function work(as an algorithm)?

The reason answering your question is especially tricky, or at least in detail, is because there is no specification that says which sorting algorithm a browser should implement. So telling you specifically how it works on one browser may differ between browsers, or even change over time.

The gist of it is though, you want to think of "a" and "b" as being any two values. If you are returning the result of "a" - "b", then your sort goes in ascending order. If you do "b" - "a", then it is in descending order.

The neat thing about making your own sort functions, is that you can compare the value of "a" and "b" after processing them in a separate function. So lets say you want to sort by the Celsius values, but your array in only in Fahrenheit. You can do something like:

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

How does JavaScript's sort (compareFunction) work?

It depends on the implementation. This actual implementation, looks like an insertion sort, with this amount of data (it could be different, like with Chrome, and the different implementation for less than 10 items or more items), is going from index zero to the end and if a swap has not taken place at the last two items, then it stops, otherwise it goes backwards to index zero.

Basically it tests and changes in this order

5   2   1 -10   8   original order
5   2
    2   1
        1 -10
          -10   8   swap
            8 -10
        1   8       swap
        8   1
    2   8           swap
    8   2
5   8               swap
8   5  2    1 -10   result

A more complex sorting shows better what is going on, with two greater values, which need to move to the other side of the array

8   9   1   2   3   4   original array
8   9
    9   1               swap
    1   9
8   1                   swap
1   8
        9   2           swap
        2   9
    8   2               swap
    2   8
1   2
            9   3       swap
            3   9
        8   3           swap
        3   8
    2   3
                9   4   swap
                4   9
            8   4       swap
            4   8
        3   4
1   2   3   4   8   9   result

Live example, does not work in all user agents (eg not in Edge, but in Chrome)

var array = [8, 9, 1, 2, 3, 4];console.log(JSON.stringify(array));array.sort(function (a, b) {    console.log(a , b, JSON.stringify(array));    return a - b;});console.log(JSON.stringify(array));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Why does compare function of sort() work like that?

Your interpreation of the docs is wrong.

You say

-1 means elements should stay in the same place.

That's wrong, the docs just state that -1 means a should be sorted before b.

Depending on the underlying sorting algorithm, there is no guarantee whatsoever that, when calling the comparefunction with parameters a and b that a is currently before b in the array. Ie imagine an array [1,2,3]. It may be possible that the compare function is called with parameters (3, 1) or (1,3). But if you return -1 in the first case, 1 and 3 will indeed switch positions. And vice versa, if you return 1 in the second case, 1 and 3 will again switch places.

EDIT

Different browser implement sort differently. For instance if you execute the following snippet in chrome and in firefox you will get different results.

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort((a,b) => {
    console.log(`${a}  ${b}`);
  return 1;
})
console.log(arr);

Sorting an array - passing a compare function

You can add special handling for zeroes:

var compare = function(nodeA, nodeB) {  // in case both sides are equal  if (nodeA.index === nodeB.index) {    return 0;  }  if (nodeA.index === 0) {    return 1;  }  if (nodeB.index === 0) {    return -1;  }
  return +nodeA.index - +nodeB.index;};
var data = [{  index: 2,  value: 'a'}, {  index: 0,  value: 'b'}, {  index: 3,  value: 'c'}, {  index: 1,  value: 'd'}]
data.sort(compare);
console.log(data);

Sorting array with sort function

It doesn't output [2, 3, 4, 5] it outputs 2, 3, 4 and 5 each in a separate step of the iteration. If you also log order you'll see that the array still contains [1, 2, 3, 4, 5]. The comparator function receives two elements of the array that it compares to each other. That way it knows in which order those elements should be. If you only log a and not b, you'll wont see all the information that is passed to the comparator. If you log both a and b, you'll see that also 1 is passed, to parameter b.

let numbers = [1, 2, 3, 4, 5]
let order = numbers.sort((a, b) => {
    console.log('Comparing', a, b);
});

console.log('Final result', order);

Javascript sort function not sorting

Your compare function is returning a boolean. Array.sort() expects you to return a number.

If your compare functions returns a value < 0, 'a' will be placed before 'b'.

If your compare functions returns a value > 0, 'b' will be placed before 'a'.

If your compare functions returns 0, the order will remain as-is.

So, to sort by number of stars in descending order, you could do this:

this.topPlayers.sort((a, b) => b.stars - a.stars);

If 'a' has more stars than 'b', the return value will be negative, and 'a' will be sorted before 'b', and vice versa.

---

Related Topics