How does Javascript's sort() work?
Is the array sort callback function called many times during the course of the sort?
Yes
If so, I'd like to know which two numbers are passed into the function each time
You could find out your self with:
array.sort((a,b) => {
console.log(`comparing ${a},${b}`);
return a > b ? 1
: a === b ? 0
: -1;
});
EDIT
This is the output I've got:
25,8
25,7
8,7
25,41
How does sort() works in JavaScript?
See MDN:
The default sort order is according to string Unicode code points.
And when you sort by string, 100
is smaller than 20
because it tests character-by-character.
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 sorting a JS array of numbers with work?
This sort works on your input array due to its small size and the current implementation of sort
in Chrome V8 (and, likely, other browsers).
The return value of the comparator function is defined in the documentation:
- If
compareFunction(a, b)
is less than 0, sorta
to an index lower than
b
, i.e.a
comes first.- If
compareFunction(a, b)
returns 0, leavea
and
b
unchanged with respect to each other, but sorted with respect to all
different elements.- If
compareFunction(a, b)
is greater than 0, sortb
to an index lower thana
, i.e.b
comes first.
However, your function returns binary true
or false
, which evaluate to 1
or 0
respectively when compared to a number. This effectively lumps comparisons where n1 < n2
in with n1 === n2
, claiming both to be even. If n1
is 9 and n2
is 3, 9 < 3 === false
or 0
. In other words, your sort leaves 9 and 3 "unchanged with respect to each other" rather than insisting "sort 9 to an index lower than 3".
If your array is shorter than 11 elements, Chrome V8's sort routine switches immediately to an insertion sort and performs no quicksort steps:
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
V8's insertion sort implementation only cares if the comparator function reports b
as greater than a
, taking the same else
branch for both 0
and < 0
comparator returns:
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
Quicksort's implementation, however, relies on all three comparisons both in choosing a pivot and in partitioning:
var order = comparefn(element, pivot);
if (order < 0) {
// ...
} else if (order > 0) {
// ...
}
// move on to the next iteration of the partition loop
This guarantees an accurate sort on arrays such as [1,3,2,4]
, and dooms arrays with more than 10 elements to at least one almost certainly inaccurate step of quicksort.
Update 7/19/19: Since the version of V8 (6) discussed in this answer, implementation of V8's array sort moved to Torque/Timsort in 7.0 as discussed in this blog post and insertion sort is called on arrays of length 22 or less.
The article linked above describes the historical situation of V8 sorting as it existed at the time of the question:
Array.prototype.sort
andTypedArray.prototype.sort
relied on the same Quicksort implementation written in JavaScript. The sorting algorithm itself is rather straightforward: The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10. Insertion Sort is more efficient for smaller arrays. This is because Quicksort gets called recursively twice after partitioning. Each such recursive call had the overhead of creating (and discarding) a stack frame.
Regardless of any changes in the implementation details, if the sort comparator adheres to standard, the code will sort predictably, but if the comparator doesn't fulfill the contract, all bets are off.
How does this JavaScript sort function work?
- sort() is an array utility function used to sort array values according to conditionals.
- If
sort()
is called without passing an anonymous function or named function, the values are sorted according to each character'sUnicode
code point value by default. In javascript, you can pass functions either anonymously(
function(){...}
) or by name like:function myFunction(){}
[].sort(myFunction);
Note, you only pass the function name and not like
myFunction()
becuase this will execute the function and pass in what is returned(which is not what we want)In the callback function passed into
sort()
, for example,compare(a,b)
, returning-1
-> a is less than b0
-> a is equal to b1
-> a is greatar than b
Related Topics
Sort Array by Firstname (Alphabetically) in JavaScript
JavaScript Regex - Look Behind Alternative
How to Access the First Property of a JavaScript Object
How to Download a File with Angular2 or Greater
Invariant Violation: Objects Are Not Valid as a React Child
How to Filter Multiple Values (Or Operation) in Angularjs
Are Trailing Commas in Arrays and Objects Part of the Spec
Why Is Mutating the [[Prototype]] of an Object Bad for Performance
How to Handle Anchor Hash Linking in Angularjs
How to Add a Custom Right-Click Menu to a Webpage
How to Fix Error: Listen Eaddrinuse While Using Nodejs
Call ASP.NET Function from JavaScript
How to Pass JSON Post Data to Web API Method as an Object
Concrete JavaScript Regular Expression for Accented Characters (Diacritics)
Iframe Src Change Event Detection