up vote 7 down vote favorite
2

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.

link|flag

6 Answers

up vote 5 down vote accepted

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

link|flag
up vote 5 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.

link|flag
up vote 2 down vote

I've just had a look at the WebKit (Safari …) source. A comment in the code specifies the sorting used:

// "Min" sort. Not the fastest, but definitely less code than heapsort
// or quicksort, and much less swapping than bubblesort/insertionsort.

I can't make head nor tail of this. Anyway, looking at the code, there are two nested loops, i = 1…n and j = i…n. So the running time is quadratic.

link|flag
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
@chmod700: Thanks for the note. They changed the directory name. I've updated the link. – Konrad Rudolph Apr 1 '09 at 8:49
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. – quixoto Sep 4 at 22:59
up vote 1 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.

link|flag
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
up vote 0 down vote

After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code at http://snipr.com/4o3va.

link|flag
up vote -2 down vote

I would imagine it is implemented with quicksort. Most library sorts are.

link|flag

Your Answer

get an OpenID
or
never shown

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