Javascript Array.sort implementation?

Multi tool use
Multi tool use












187















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





























    187















    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



























      187












      187








      187


      59






      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
















      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.







      javascript algorithm arrays sorting






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Jan 28 '14 at 14:18









      Francisc

      35.7k50159251




      35.7k50159251










      asked Oct 24 '08 at 18:08









      latortugalatortuga

      1,1512814




      1,1512814
























          7 Answers
          7






          active

          oldest

          votes


















          57














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






          share|improve this answer





















          • 102





            This should not be the accepted answer.

            – Domi
            Jan 7 '14 at 9:29






          • 2





            Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

            – Patrick Roberts
            Nov 27 '18 at 19:04



















          250














          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

































            27














            There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.



            V8 Engine Source



            From Lines 807 - 891



              var QuickSort = function QuickSort(a, from, to) {
            var third_index = 0;
            while (true) {
            // Insertion sort is faster for short arrays.
            if (to - from <= 10) {
            InsertionSort(a, from, to);
            return;
            }
            if (to - from > 1000) {
            third_index = GetThirdIndex(a, from, to);
            } else {
            third_index = from + ((to - from) >> 1);
            }
            // Find a pivot as the median of first, last and middle element.
            var v0 = a[from];
            var v1 = a[to - 1];
            var v2 = a[third_index];
            var c01 = comparefn(v0, v1);
            if (c01 > 0) {
            // v1 < v0, so swap them.
            var tmp = v0;
            v0 = v1;
            v1 = tmp;
            } // v0 <= v1.
            var c02 = comparefn(v0, v2);
            if (c02 >= 0) {
            // v2 <= v0 <= v1.
            var tmp = v0;
            v0 = v2;
            v2 = v1;
            v1 = tmp;
            } else {
            // v0 <= v1 && v0 < v2
            var c12 = comparefn(v1, v2);
            if (c12 > 0) {
            // v0 <= v2 < v1
            var tmp = v1;
            v1 = v2;
            v2 = tmp;
            }
            }
            // v0 <= v1 <= v2
            a[from] = v0;
            a[to - 1] = v2;
            var pivot = v1;
            var low_end = from + 1; // Upper bound of elements lower than pivot.
            var high_start = to - 1; // Lower bound of elements greater than pivot.
            a[third_index] = a[low_end];
            a[low_end] = pivot;

            // From low_end to i are elements equal to pivot.
            // From i to high_start are elements that haven't been compared yet.
            partition: for (var i = low_end + 1; i < high_start; i++) {
            var element = a[i];
            var order = comparefn(element, pivot);
            if (order < 0) {
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
            } else if (order > 0) {
            do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
            } while (order > 0);
            a[i] = a[high_start];
            a[high_start] = element;
            if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
            }
            }
            }
            if (to - high_start < low_end - from) {
            QuickSort(a, high_start, to);
            to = low_end;
            } else {
            QuickSort(a, from, low_end);
            from = high_start;
            }
            }
            };


            Update
            As of 2018 V8 uses TimSort, thanks @celwell. Source






            share|improve this answer





















            • 1





              I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

              – celwell
              Jan 1 at 1:18











            • You are absolutely right, will update answer.

              – Joe Thomas
              Jan 1 at 3:50



















            20














            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



















            • 14





              Update: Recent Firefoxes have a stable Array.sort; see this question.

              – skagedal
              Jan 24 '12 at 13:54













            • The point is that the sorting algorithm is implementation-dependent.

              – sean
              Sep 23 '17 at 15:18



















            8














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






            share|improve this answer

































              6














              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






              • 1





                @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



















              3














              As of V8 v7.0 / Chrome 70, V8 uses TimSort, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.



              See the the post on the V8 dev blog for details about this change. You can also read the source code or patch 1186801.






              share|improve this answer






















                protected by Praveen Apr 21 '16 at 12:33



                Thank you for your interest in this question.
                Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                Would you like to answer one of these unanswered questions instead?














                7 Answers
                7






                active

                oldest

                votes








                7 Answers
                7






                active

                oldest

                votes









                active

                oldest

                votes






                active

                oldest

                votes









                57














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






                share|improve this answer





















                • 102





                  This should not be the accepted answer.

                  – Domi
                  Jan 7 '14 at 9:29






                • 2





                  Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                  – Patrick Roberts
                  Nov 27 '18 at 19:04
















                57














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






                share|improve this answer





















                • 102





                  This should not be the accepted answer.

                  – Domi
                  Jan 7 '14 at 9:29






                • 2





                  Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                  – Patrick Roberts
                  Nov 27 '18 at 19:04














                57












                57








                57







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






                share|improve this answer















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







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Oct 25 '08 at 14:10









                Bill the Lizard

                293k157496788




                293k157496788










                answered Oct 24 '08 at 18:43









                BrittonBritton

                72254




                72254








                • 102





                  This should not be the accepted answer.

                  – Domi
                  Jan 7 '14 at 9:29






                • 2





                  Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                  – Patrick Roberts
                  Nov 27 '18 at 19:04














                • 102





                  This should not be the accepted answer.

                  – Domi
                  Jan 7 '14 at 9:29






                • 2





                  Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                  – Patrick Roberts
                  Nov 27 '18 at 19:04








                102




                102





                This should not be the accepted answer.

                – Domi
                Jan 7 '14 at 9:29





                This should not be the accepted answer.

                – Domi
                Jan 7 '14 at 9:29




                2




                2





                Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                – Patrick Roberts
                Nov 27 '18 at 19:04





                Well it's also wrong in that it only states an algorithm for a specific implementation. The specification makes no such claims, and other implementations use other algorithms, so this is quite misleading.

                – Patrick Roberts
                Nov 27 '18 at 19:04













                250














                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






























                  250














                  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




























                    250












                    250








                    250







                    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















                    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














                    share|improve this answer



                    share|improve this answer








                    edited May 23 '17 at 12:10









                    Community

                    11




                    11










                    answered Oct 25 '08 at 15:02









                    Konrad RudolphKonrad Rudolph

                    398k1017871034




                    398k1017871034























                        27














                        There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.



                        V8 Engine Source



                        From Lines 807 - 891



                          var QuickSort = function QuickSort(a, from, to) {
                        var third_index = 0;
                        while (true) {
                        // Insertion sort is faster for short arrays.
                        if (to - from <= 10) {
                        InsertionSort(a, from, to);
                        return;
                        }
                        if (to - from > 1000) {
                        third_index = GetThirdIndex(a, from, to);
                        } else {
                        third_index = from + ((to - from) >> 1);
                        }
                        // Find a pivot as the median of first, last and middle element.
                        var v0 = a[from];
                        var v1 = a[to - 1];
                        var v2 = a[third_index];
                        var c01 = comparefn(v0, v1);
                        if (c01 > 0) {
                        // v1 < v0, so swap them.
                        var tmp = v0;
                        v0 = v1;
                        v1 = tmp;
                        } // v0 <= v1.
                        var c02 = comparefn(v0, v2);
                        if (c02 >= 0) {
                        // v2 <= v0 <= v1.
                        var tmp = v0;
                        v0 = v2;
                        v2 = v1;
                        v1 = tmp;
                        } else {
                        // v0 <= v1 && v0 < v2
                        var c12 = comparefn(v1, v2);
                        if (c12 > 0) {
                        // v0 <= v2 < v1
                        var tmp = v1;
                        v1 = v2;
                        v2 = tmp;
                        }
                        }
                        // v0 <= v1 <= v2
                        a[from] = v0;
                        a[to - 1] = v2;
                        var pivot = v1;
                        var low_end = from + 1; // Upper bound of elements lower than pivot.
                        var high_start = to - 1; // Lower bound of elements greater than pivot.
                        a[third_index] = a[low_end];
                        a[low_end] = pivot;

                        // From low_end to i are elements equal to pivot.
                        // From i to high_start are elements that haven't been compared yet.
                        partition: for (var i = low_end + 1; i < high_start; i++) {
                        var element = a[i];
                        var order = comparefn(element, pivot);
                        if (order < 0) {
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        } else if (order > 0) {
                        do {
                        high_start--;
                        if (high_start == i) break partition;
                        var top_elem = a[high_start];
                        order = comparefn(top_elem, pivot);
                        } while (order > 0);
                        a[i] = a[high_start];
                        a[high_start] = element;
                        if (order < 0) {
                        element = a[i];
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        }
                        }
                        }
                        if (to - high_start < low_end - from) {
                        QuickSort(a, high_start, to);
                        to = low_end;
                        } else {
                        QuickSort(a, from, low_end);
                        from = high_start;
                        }
                        }
                        };


                        Update
                        As of 2018 V8 uses TimSort, thanks @celwell. Source






                        share|improve this answer





















                        • 1





                          I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                          – celwell
                          Jan 1 at 1:18











                        • You are absolutely right, will update answer.

                          – Joe Thomas
                          Jan 1 at 3:50
















                        27














                        There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.



                        V8 Engine Source



                        From Lines 807 - 891



                          var QuickSort = function QuickSort(a, from, to) {
                        var third_index = 0;
                        while (true) {
                        // Insertion sort is faster for short arrays.
                        if (to - from <= 10) {
                        InsertionSort(a, from, to);
                        return;
                        }
                        if (to - from > 1000) {
                        third_index = GetThirdIndex(a, from, to);
                        } else {
                        third_index = from + ((to - from) >> 1);
                        }
                        // Find a pivot as the median of first, last and middle element.
                        var v0 = a[from];
                        var v1 = a[to - 1];
                        var v2 = a[third_index];
                        var c01 = comparefn(v0, v1);
                        if (c01 > 0) {
                        // v1 < v0, so swap them.
                        var tmp = v0;
                        v0 = v1;
                        v1 = tmp;
                        } // v0 <= v1.
                        var c02 = comparefn(v0, v2);
                        if (c02 >= 0) {
                        // v2 <= v0 <= v1.
                        var tmp = v0;
                        v0 = v2;
                        v2 = v1;
                        v1 = tmp;
                        } else {
                        // v0 <= v1 && v0 < v2
                        var c12 = comparefn(v1, v2);
                        if (c12 > 0) {
                        // v0 <= v2 < v1
                        var tmp = v1;
                        v1 = v2;
                        v2 = tmp;
                        }
                        }
                        // v0 <= v1 <= v2
                        a[from] = v0;
                        a[to - 1] = v2;
                        var pivot = v1;
                        var low_end = from + 1; // Upper bound of elements lower than pivot.
                        var high_start = to - 1; // Lower bound of elements greater than pivot.
                        a[third_index] = a[low_end];
                        a[low_end] = pivot;

                        // From low_end to i are elements equal to pivot.
                        // From i to high_start are elements that haven't been compared yet.
                        partition: for (var i = low_end + 1; i < high_start; i++) {
                        var element = a[i];
                        var order = comparefn(element, pivot);
                        if (order < 0) {
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        } else if (order > 0) {
                        do {
                        high_start--;
                        if (high_start == i) break partition;
                        var top_elem = a[high_start];
                        order = comparefn(top_elem, pivot);
                        } while (order > 0);
                        a[i] = a[high_start];
                        a[high_start] = element;
                        if (order < 0) {
                        element = a[i];
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        }
                        }
                        }
                        if (to - high_start < low_end - from) {
                        QuickSort(a, high_start, to);
                        to = low_end;
                        } else {
                        QuickSort(a, from, low_end);
                        from = high_start;
                        }
                        }
                        };


                        Update
                        As of 2018 V8 uses TimSort, thanks @celwell. Source






                        share|improve this answer





















                        • 1





                          I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                          – celwell
                          Jan 1 at 1:18











                        • You are absolutely right, will update answer.

                          – Joe Thomas
                          Jan 1 at 3:50














                        27












                        27








                        27







                        There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.



                        V8 Engine Source



                        From Lines 807 - 891



                          var QuickSort = function QuickSort(a, from, to) {
                        var third_index = 0;
                        while (true) {
                        // Insertion sort is faster for short arrays.
                        if (to - from <= 10) {
                        InsertionSort(a, from, to);
                        return;
                        }
                        if (to - from > 1000) {
                        third_index = GetThirdIndex(a, from, to);
                        } else {
                        third_index = from + ((to - from) >> 1);
                        }
                        // Find a pivot as the median of first, last and middle element.
                        var v0 = a[from];
                        var v1 = a[to - 1];
                        var v2 = a[third_index];
                        var c01 = comparefn(v0, v1);
                        if (c01 > 0) {
                        // v1 < v0, so swap them.
                        var tmp = v0;
                        v0 = v1;
                        v1 = tmp;
                        } // v0 <= v1.
                        var c02 = comparefn(v0, v2);
                        if (c02 >= 0) {
                        // v2 <= v0 <= v1.
                        var tmp = v0;
                        v0 = v2;
                        v2 = v1;
                        v1 = tmp;
                        } else {
                        // v0 <= v1 && v0 < v2
                        var c12 = comparefn(v1, v2);
                        if (c12 > 0) {
                        // v0 <= v2 < v1
                        var tmp = v1;
                        v1 = v2;
                        v2 = tmp;
                        }
                        }
                        // v0 <= v1 <= v2
                        a[from] = v0;
                        a[to - 1] = v2;
                        var pivot = v1;
                        var low_end = from + 1; // Upper bound of elements lower than pivot.
                        var high_start = to - 1; // Lower bound of elements greater than pivot.
                        a[third_index] = a[low_end];
                        a[low_end] = pivot;

                        // From low_end to i are elements equal to pivot.
                        // From i to high_start are elements that haven't been compared yet.
                        partition: for (var i = low_end + 1; i < high_start; i++) {
                        var element = a[i];
                        var order = comparefn(element, pivot);
                        if (order < 0) {
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        } else if (order > 0) {
                        do {
                        high_start--;
                        if (high_start == i) break partition;
                        var top_elem = a[high_start];
                        order = comparefn(top_elem, pivot);
                        } while (order > 0);
                        a[i] = a[high_start];
                        a[high_start] = element;
                        if (order < 0) {
                        element = a[i];
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        }
                        }
                        }
                        if (to - high_start < low_end - from) {
                        QuickSort(a, high_start, to);
                        to = low_end;
                        } else {
                        QuickSort(a, from, low_end);
                        from = high_start;
                        }
                        }
                        };


                        Update
                        As of 2018 V8 uses TimSort, thanks @celwell. Source






                        share|improve this answer















                        There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.



                        V8 Engine Source



                        From Lines 807 - 891



                          var QuickSort = function QuickSort(a, from, to) {
                        var third_index = 0;
                        while (true) {
                        // Insertion sort is faster for short arrays.
                        if (to - from <= 10) {
                        InsertionSort(a, from, to);
                        return;
                        }
                        if (to - from > 1000) {
                        third_index = GetThirdIndex(a, from, to);
                        } else {
                        third_index = from + ((to - from) >> 1);
                        }
                        // Find a pivot as the median of first, last and middle element.
                        var v0 = a[from];
                        var v1 = a[to - 1];
                        var v2 = a[third_index];
                        var c01 = comparefn(v0, v1);
                        if (c01 > 0) {
                        // v1 < v0, so swap them.
                        var tmp = v0;
                        v0 = v1;
                        v1 = tmp;
                        } // v0 <= v1.
                        var c02 = comparefn(v0, v2);
                        if (c02 >= 0) {
                        // v2 <= v0 <= v1.
                        var tmp = v0;
                        v0 = v2;
                        v2 = v1;
                        v1 = tmp;
                        } else {
                        // v0 <= v1 && v0 < v2
                        var c12 = comparefn(v1, v2);
                        if (c12 > 0) {
                        // v0 <= v2 < v1
                        var tmp = v1;
                        v1 = v2;
                        v2 = tmp;
                        }
                        }
                        // v0 <= v1 <= v2
                        a[from] = v0;
                        a[to - 1] = v2;
                        var pivot = v1;
                        var low_end = from + 1; // Upper bound of elements lower than pivot.
                        var high_start = to - 1; // Lower bound of elements greater than pivot.
                        a[third_index] = a[low_end];
                        a[low_end] = pivot;

                        // From low_end to i are elements equal to pivot.
                        // From i to high_start are elements that haven't been compared yet.
                        partition: for (var i = low_end + 1; i < high_start; i++) {
                        var element = a[i];
                        var order = comparefn(element, pivot);
                        if (order < 0) {
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        } else if (order > 0) {
                        do {
                        high_start--;
                        if (high_start == i) break partition;
                        var top_elem = a[high_start];
                        order = comparefn(top_elem, pivot);
                        } while (order > 0);
                        a[i] = a[high_start];
                        a[high_start] = element;
                        if (order < 0) {
                        element = a[i];
                        a[i] = a[low_end];
                        a[low_end] = element;
                        low_end++;
                        }
                        }
                        }
                        if (to - high_start < low_end - from) {
                        QuickSort(a, high_start, to);
                        to = low_end;
                        } else {
                        QuickSort(a, from, low_end);
                        from = high_start;
                        }
                        }
                        };


                        Update
                        As of 2018 V8 uses TimSort, thanks @celwell. Source







                        share|improve this answer














                        share|improve this answer



                        share|improve this answer








                        edited Jan 1 at 3:52

























                        answered May 16 '16 at 0:37









                        Joe ThomasJoe Thomas

                        2,27231533




                        2,27231533








                        • 1





                          I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                          – celwell
                          Jan 1 at 1:18











                        • You are absolutely right, will update answer.

                          – Joe Thomas
                          Jan 1 at 3:50














                        • 1





                          I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                          – celwell
                          Jan 1 at 1:18











                        • You are absolutely right, will update answer.

                          – Joe Thomas
                          Jan 1 at 3:50








                        1




                        1





                        I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                        – celwell
                        Jan 1 at 1:18





                        I believe V8 is now using TimSort: github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/…

                        – celwell
                        Jan 1 at 1:18













                        You are absolutely right, will update answer.

                        – Joe Thomas
                        Jan 1 at 3:50





                        You are absolutely right, will update answer.

                        – Joe Thomas
                        Jan 1 at 3:50











                        20














                        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



















                        • 14





                          Update: Recent Firefoxes have a stable Array.sort; see this question.

                          – skagedal
                          Jan 24 '12 at 13:54













                        • The point is that the sorting algorithm is implementation-dependent.

                          – sean
                          Sep 23 '17 at 15:18
















                        20














                        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



















                        • 14





                          Update: Recent Firefoxes have a stable Array.sort; see this question.

                          – skagedal
                          Jan 24 '12 at 13:54













                        • The point is that the sorting algorithm is implementation-dependent.

                          – sean
                          Sep 23 '17 at 15:18














                        20












                        20








                        20







                        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













                        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












                        share|improve this answer



                        share|improve this answer










                        answered Oct 24 '08 at 18:34







                        Steve















                        • 14





                          Update: Recent Firefoxes have a stable Array.sort; see this question.

                          – skagedal
                          Jan 24 '12 at 13:54













                        • The point is that the sorting algorithm is implementation-dependent.

                          – sean
                          Sep 23 '17 at 15:18














                        • 14





                          Update: Recent Firefoxes have a stable Array.sort; see this question.

                          – skagedal
                          Jan 24 '12 at 13:54













                        • The point is that the sorting algorithm is implementation-dependent.

                          – sean
                          Sep 23 '17 at 15:18








                        14




                        14





                        Update: Recent Firefoxes have a stable Array.sort; see this question.

                        – skagedal
                        Jan 24 '12 at 13:54







                        Update: Recent Firefoxes have a stable Array.sort; see this question.

                        – skagedal
                        Jan 24 '12 at 13:54















                        The point is that the sorting algorithm is implementation-dependent.

                        – sean
                        Sep 23 '17 at 15:18





                        The point is that the sorting algorithm is implementation-dependent.

                        – sean
                        Sep 23 '17 at 15:18











                        8














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






                        share|improve this answer






























                          8














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






                          share|improve this answer




























                            8












                            8








                            8







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






                            share|improve this answer















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







                            share|improve this answer














                            share|improve this answer



                            share|improve this answer








                            edited Jul 24 '16 at 1:17









                            Genzume

                            3,12511425




                            3,12511425










                            answered Oct 24 '08 at 18:42









                            latortugalatortuga

                            1,1512814




                            1,1512814























                                6














                                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






                                • 1





                                  @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
















                                6














                                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






                                • 1





                                  @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














                                6












                                6








                                6







                                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













                                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












                                share|improve this answer



                                share|improve this answer










                                answered Oct 24 '08 at 18:14









                                Huibert GillHuibert Gill

                                69358




                                69358













                                • 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






                                • 1





                                  @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



















                                • 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






                                • 1





                                  @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

















                                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





                                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




                                1




                                1





                                @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





                                @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





                                My bad, I misunderstood the point of his question.

                                – Jason Bunting
                                Oct 24 '08 at 19:06











                                3














                                As of V8 v7.0 / Chrome 70, V8 uses TimSort, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.



                                See the the post on the V8 dev blog for details about this change. You can also read the source code or patch 1186801.






                                share|improve this answer




























                                  3














                                  As of V8 v7.0 / Chrome 70, V8 uses TimSort, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.



                                  See the the post on the V8 dev blog for details about this change. You can also read the source code or patch 1186801.






                                  share|improve this answer


























                                    3












                                    3








                                    3







                                    As of V8 v7.0 / Chrome 70, V8 uses TimSort, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.



                                    See the the post on the V8 dev blog for details about this change. You can also read the source code or patch 1186801.






                                    share|improve this answer













                                    As of V8 v7.0 / Chrome 70, V8 uses TimSort, Python's sorting algorithm. Chrome 70 was released on September 13, 2018.



                                    See the the post on the V8 dev blog for details about this change. You can also read the source code or patch 1186801.







                                    share|improve this answer












                                    share|improve this answer



                                    share|improve this answer










                                    answered Dec 21 '18 at 1:15









                                    BorisBoris

                                    1,31511427




                                    1,31511427

















                                        protected by Praveen Apr 21 '16 at 12:33



                                        Thank you for your interest in this question.
                                        Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                                        Would you like to answer one of these unanswered questions instead?



                                        7a70pOP mCc7FuGmHysB,33gO EB hQTDlDiHP,cbASg0RZ,S nNJAK1
                                        ghub4K5pOc,pNFGF5MIVHDv4 zds0 z7,WrTpUISKT,iCmA3JSYSguAyQFrjO,A5iBS1sEzlcFpokgYdEArjXsI

                                        Popular posts from this blog

                                        Monofisismo

                                        Angular Downloading a file using contenturl with Basic Authentication

                                        Olmecas