Javascript Array.sort implementation?

Question

6

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.

edited Nov 11 '08 at 8:07

dbr
16.6k22979

asked Oct 24 '08 at 18:08

latortuga
5515

Bill the Lizard · Answer 1 · 2008-10-25 14:10:59Z

5

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

edited Oct 25 '08 at 14:10

Bill the Lizard♦
55.2k1798222

answered Oct 24 '08 at 18:43

Britton
663

Steve · Answer 2 · 2008-10-24 18:34:59Z

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.

HuibertGill · Answer 3 · 2008-10-24 18:14:26Z

1

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.

answered Oct 24 '08 at 18:14

HuibertGill
27615

	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 Oct 24 '08 at 18:50
	My bad, I misunderstood the point of his question. – Jason Bunting Oct 24 '08 at 19:06

Konrad Rudolph · Answer 4 · 2009-04-01 08:48:56Z

1

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.

edited Apr 1 '09 at 8:48

answered Oct 25 '08 at 15:02

Konrad Rudolph
66.9k7121259

	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

latortuga · Answer 5 · 2008-10-24 18:42:13Z

0

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

answered Oct 24 '08 at 18:42

latortuga
5515

Mark Lubin · Answer 6 · 2008-10-24 18:26:11Z

-2

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

answered Oct 24 '08 at 18:26

Mark Lubin
822527

Javascript Array.sort implementation?

6 Answers

Your Answer

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

Hello World!

Linked

Related