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.
+1
A:
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.
HuibertGill
2008-10-24 18:14:26
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
2008-10-24 18:20:00
@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ć
2008-10-24 18:50:51
My bad, I misunderstood the point of his question.
Jason Bunting
2008-10-24 19:06:16
A:
I would imagine it is implemented with quicksort. Most library sorts are.
Mark Lubin
2008-10-24 18:26:11
+5
A:
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.
A:
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code at http://snipr.com/4o3va.
latortuga
2008-10-24 18:42:13
+2
A:
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.
Konrad Rudolph
2008-10-25 15:02:50
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
2008-10-25 15:52:00
Strange comment to find indeed. But quicksort is ~7 lines in most languages. Also your source link appears to be broken.
Trey Stout
2009-04-01 03:10:38
@chmod700: Thanks for the note. They changed the directory name. I've updated the link.
Konrad Rudolph
2009-04-01 08:49:27
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
2010-09-04 22:59:58