# Javascript Array.sort implementation?

Which algorithm does the JavaScript `Array#sort()` function use? I understand that it can take all manner of arguments and functions to perform different kinds of sorts, I'm simply interested in which algorithm the vanilla sort uses.

89

I've just had a look at the WebKit (Chrome, Safari …) source. Depending on the type of array, different sort methods are used:

Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function `std::qsort` which implements some variation of quicksort (usually introsort).

Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or `qsort` if no merge sort is available.

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call “min” sort) or, in some cases, it sorts via an AVL tree. Unfortunately, the documentation here is rather vague so you’d have to trace the code paths to actually see for which types which sort method is used.

And then there are gems like this comment:

``````// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).
``````

– Let’s just hope that whoever actually “fixes” this has a better understanding of asymptotic runtime than the writer of this comment, and realises that radix sort has a slightly more complex runtime description than simply O(N).

(Thanks to phsource for pointing out the error in the original answer.)

Tuesday, June 1, 2021

17

Use `Array`'s `sort()` method, eg

``````myArray.sort(function(a, b) {
return a.distance - b.distance;
});
``````
Tuesday, June 22, 2021

33

I believe Pako (https://github.com/nodeca/pako) is now the fastest javascript implementation of deflate and other zlib methods (inflate / gzip / ungzip). There are benchmarks on the github page. It also supports chunking if you need to work with big blobs.

Disclaimer: I am the author of this code.

Wednesday, July 28, 2021

43

In your first block of code, you are returning an object, which is different from `this` or `self`.

You don't necessarily have to return `this` in your constructors but you should assign your functions on the returned object. If you create a variable for the object you want to return, you can use it in your `setTimeout` callback like so:

``````var class1 = function(val1)
{
var val = val1;

var obj = {
f1: function()
{
return val;
},
onEvent: function()
{
console.log('not implemented yet. Override');
}
};

setTimeout(function()
{
obj.onEvent();

}, 1000);

return obj;
};
``````

For extra style points, you might want to capitalize the name of your constructors (and perhaps use `new` to instantiate them to make things clearer to your readers).

Tuesday, August 31, 2021

48

You can use sort like this:

``````arr.sort((a,b) => {
return a < b // To sort in descending order
// return a > b // To sort in ascending order
})
``````

Example:

``````var arr = [
['foo', 'fifth', 5],
['fee', 'seventh', 7],
['faa', 'third', 3]
];

var sortedArr = arr.sort(function(a,b){
return a < b
});

console.log(sortedArr)``````

# Here's how sort function work

First, let's assume this array:

``````[1,2] // where a = 1, b = 2
``````

Ascending order:

Is a greater than b?

If it is yes, we need to sort => return true

Else, we don't need to sort => return false

Descending order:

Is a lesser than b?

If it is yes, we need to sort => return true

Else, we don't need to sort => return false

In preceding example, we're verifying if a is lesser than b, then return true to sort it out else return false as this is already in descending order.

As per @Nina Scholz

Please do not return a Boolean value for sorting, because sort needs a value smaller than zero, zero or greater than zero. To omit equal cases may actually work, but it make for the algorithm harder to get the array to sort.

You should consider returning 0, 1, or -1. For your case, you should use like this:

``````arr.sort((a,b) => {
if(a < b) return 1
if(a > b) return -1
if(a === b) return 0
})
``````

Furthermore

If the values are only integers (doesn't contain Infinity and NaN), then it can be simplifies as below,

``````arr.sort((a,b) => b-a)
``````
Tuesday, August 31, 2021