up vote 42 down vote favorite
14

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.

share|improve this question
feedback

5 Answers

up vote 25 down vote accepted

If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.

share|improve this answer
feedback
up vote 31 down vote

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.)

share|improve this answer
In Min Sort, you repeatedly find the minimum element of the array from current position upto the end and swap it with the element at the current position. Among the two nested loops the inner loop is for finding the minimum from current position upto the end. (the j = i+1 to n loop) – Vijay Dev Oct 25 '08 at 15:52
Strange comment to find indeed. But quicksort is ~7 lines in most languages. Also your source link appears to be broken. – Trey Stout Apr 1 '09 at 3:10
33  
Wow, this is stunning. There are lots of great reasons for choosing one sort over others, but for an A-grade browser used by millions of people, I'm stunned that "less code" is the rationale for this here. – Ben Zotto Sep 4 '10 at 22:59
4  
This is called Selection Sort. – Alexey Lebedev Mar 8 '11 at 8:13
6  
@JorenB Well, less code means less maintenance, less opportunity of introducing errors etc. So it is a valid reason, all other things being equal. Which isn’t the case here and this leads me to suspect that the actual reason for implementing this was “we don’t have time to program a proper sort function, and until somebody shows that it’s needed, we stick with a very easy, foolproof one.” – Konrad Rudolph Mar 28 '12 at 15:40
show 5 more comments
feedback
up vote 2 down vote

After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.

share|improve this answer
feedback
up vote 12 down vote

The ECMAscript standard does not specify which sort algorithm is to be used. Indeed, different browsers feature different sort algorithms. For example, Mozilla/Firefox's sort() is not stable (in the sorting sense of the word) when sorting a map. IE's sort() is stable.

share|improve this answer
4  
Update: Recent Firefoxes have a stable Array.sort; see this question. – skagedal Jan 24 '12 at 13:54
feedback
up vote 3 down vote

I think that would depend on what browser implementation you are refering to.

Every browser type has it's own javascript engine implementation, so it depends. You could check the sourcecode repos for Mozilla and Webkit/Khtml for different implementations.

IE is closed source however, so you may have to ask somebody at microsoft.

share|improve this answer
Different interpreters may do things differently in the sense that they are either buggy (i.e. it isn't on-purpose) or they add or take away features. The sort() method is a standard part of Core JavaScript and would be defined by the standard, which browsers would want to follow. – Jason Bunting Oct 24 '08 at 18:20
@JasonBunting if function is implemented and does what it should do as defined in specification, browser developers are free to implement the function as they want: be it bubble or quick sort. ECMA specs do not define sort algorithm to be used. – Damir Zekić Oct 24 '08 at 18:50
My bad, I misunderstood the point of his question. – Jason Bunting Oct 24 '08 at 19:06
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.