Javascript Array sort implementation

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

User · Answer

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

User · 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

User · 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

User · 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

User · Answer

After some more research  it appears  for Mozilla Firefox  that Array sort   uses mergesort  See the code here

User · 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  lt   10            InsertionSort a  from  to           return                if  to - from  gt  1000            third index   GetThirdIndex a  from  to           else           third index   from     to - from   gt  gt  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  gt  0               v1  lt  v0  so swap them          var tmp   v0          v0   v1          v1   tmp             v0  lt   v1        var c02   comparefn v0  v2         if  c02  gt   0               v2  lt   v0  lt   v1          var tmp   v0          v0   v2          v2   v1          v1   tmp          else              v0  lt   v1  amp  amp  v0  lt  v2         var c12   comparefn v1  v2           if  c12  gt  0                 v0  lt   v2  lt  v1           var tmp   v1            v1   v2            v2   tmp                             v0  lt   v1  lt   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  lt  high start  i              var element   a i           var order   comparefn element  pivot           if  order  lt  0              a i    a low end             a low end    element            low end              else if  order  gt  0              do               high start--              if  high start    i  break partition              var top elem   a high start               order   comparefn top elem  pivot               while  order  gt  0             a i    a high start             a high start    element            if  order  lt  0                element   a i               a i    a low end               a low end    element              low end                                        if  to - high start  lt  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

User · Answer

JavaScript s Array sort   function has internal mechanisms to selects the best sorting algorithm   QuickSort  MergeSort  etc  on the basis of the datatype of array elements

User · 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

User · Answer

try this with quick sort   function sort arr  compareFn    a  b    gt  a  lt   b         if   arr instanceof Array    arr length     0            return arr             if  typeof compareFn      function             throw new Error  compareFn is not a function                const partition    arr  low  high    gt            const pivot   arr low           while  low  lt  high                while  low  lt  high  amp  amp  compareFn pivot  arr high                      --high                            arr low    arr high               while  low  lt  high  amp  amp  compareFn arr low   pivot                       low                            arr high    arr low                     arr low    pivot          return low              const quickSort    arr  low  high    gt            if  low  lt  high                let pivot   partition arr  low  high               quickSort arr  low  pivot - 1               quickSort arr  pivot   1  high                     return arr              return quickSort arr  0  arr length - 1

User · Answer

After some more research  it appears  for Mozilla Firefox  that Array sort   uses mergesort  See the code here

User · 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

User · Answer

try this with quick sort   function sort arr  compareFn    a  b    gt  a  lt   b         if   arr instanceof Array    arr length     0            return arr             if  typeof compareFn      function             throw new Error  compareFn is not a function                const partition    arr  low  high    gt            const pivot   arr low           while  low  lt  high                while  low  lt  high  amp  amp  compareFn pivot  arr high                      --high                            arr low    arr high               while  low  lt  high  amp  amp  compareFn arr low   pivot                       low                            arr high    arr low                     arr low    pivot          return low              const quickSort    arr  low  high    gt            if  low  lt  high                let pivot   partition arr  low  high               quickSort arr  low  pivot - 1               quickSort arr  pivot   1  high                     return arr              return quickSort arr  0  arr length - 1

User · Answer

JavaScript s Array sort   function has internal mechanisms to selects the best sorting algorithm   QuickSort  MergeSort  etc  on the basis of the datatype of array elements

User · 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

User · 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  lt   10            InsertionSort a  from  to           return                if  to - from  gt  1000            third index   GetThirdIndex a  from  to           else           third index   from     to - from   gt  gt  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  gt  0               v1  lt  v0  so swap them          var tmp   v0          v0   v1          v1   tmp             v0  lt   v1        var c02   comparefn v0  v2         if  c02  gt   0               v2  lt   v0  lt   v1          var tmp   v0          v0   v2          v2   v1          v1   tmp          else              v0  lt   v1  amp  amp  v0  lt  v2         var c12   comparefn v1  v2           if  c12  gt  0                 v0  lt   v2  lt  v1           var tmp   v1            v1   v2            v2   tmp                             v0  lt   v1  lt   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  lt  high start  i              var element   a i           var order   comparefn element  pivot           if  order  lt  0              a i    a low end             a low end    element            low end              else if  order  gt  0              do               high start--              if  high start    i  break partition              var top elem   a high start               order   comparefn top elem  pivot               while  order  gt  0             a i    a high start             a high start    element            if  order  lt  0                element   a i               a i    a low end               a low end    element              low end                                        if  to - high start  lt  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

User · Answer

After some more research  it appears  for Mozilla Firefox  that Array sort   uses mergesort  See the code here

User · 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

User · 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

User · 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

User · Answer

After some more research  it appears  for Mozilla Firefox  that Array sort   uses mergesort  See the code here

User · 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

User · Answer

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

User · 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

User · Answer

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

User · 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

User · 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

User · Answer

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

User · 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

[javascript] Javascript Array.sort implementation?

Examples related to javascript

Examples related to algorithm

Examples related to arrays

Examples related to sorting