Asked  7 Months ago    Answers:  5   Viewed   35 times

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.

 Answers

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
 
dotoree
answered 7 Months ago
17

Use Array's sort() method, eg

myArray.sort(function(a, b) {
    return a.distance - b.distance;
});
Tuesday, June 22, 2021
 
macha
answered 6 Months ago
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
 
Sabya
answered 5 Months ago
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
 
IcedAnt
answered 3 Months ago
48

You can use sort like this:

arr.sort((a,b) => {
  return a[2] < b[2] // To sort in descending order
  // return a[2] > b[2] // 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[2] < b[2]
});

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[2] < b[2]) return 1
  if(a[2] > b[2]) return -1
  if(a[2] === b[2]) 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[2]-a[2])
Tuesday, August 31, 2021
 
danjah
answered 3 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share