Menu
Any idea how I can view the implementation of native javascript methods specifically the sort method. The reason why I am looking for this I am just wondering what the algorithm used is and what is the complexity of the same.
I am sorting a huge json object in javascript and I was wondering if I should write my own mety hod for the same.
Also does the implementation differ from browser to browser?
491
JavaScript by default uses insertion sort for the sort() method. This means that it is not appropriate when sorting large data sets.
In JavaScript, we can sort the elements of an array easily with a built-in method called the sort( ) function. However, data types (string, number, and so on) can differ from one array to another.
Like many other popular languages, JavaScript conveniently comes with a built-in method for sorting arrays. While the end result is the same, the various JavaScript engines implement this method using different sort algorithms: V8: Quicksort or Insertion Sort (for smaller arrays) Firefox: Merge sort.
Take a look at the WebKit implementation: https://gist.github.com/964673. Apparently, it uses min sort/selection sort. From: http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp
SpiderMonkey seems to indeed use MergeSort. See: http://hg.mozilla.org/mozilla-central/file/28be8df0deb7/js/src/jsarray.cpp.
86
Also does the implementation differ from browser to browser?
Yes, the ECMAScript standard does not specify what algorithm should be used. AFAIK Mozillas SpiderMonkey uses mergesort and WebKit uses selection sort. What IE uses you probably have to ask someone at Microsoft, since it's closed source.
And I'm willing to bet a couple of bucks that you cannot come up with a better/faster algorithm than the one implemented into the JavaScript engine of the browsers.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
