Javascript Array.sort implementation?

Multi tool use
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
add a comment |
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
add a comment |
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
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
javascript algorithm arrays sorting
edited Jan 28 '14 at 14:18
Francisc
35.7k50159251
35.7k50159251
asked Oct 24 '08 at 18:08
latortugalatortuga
1,1512814
1,1512814
add a comment |
add a comment |
7 Answers
7
active
oldest
votes
If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.
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
add a comment |
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.)
add a comment |
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
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
add a comment |
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.
14
Update: Recent Firefoxes have a stableArray.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
add a comment |
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.
add a comment |
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.
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
add a comment |
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.
add a comment |
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
If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.
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
add a comment |
If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.
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
add a comment |
If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.
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
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
add a comment |
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
add a comment |
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.)
add a comment |
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.)
add a comment |
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.)
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.)
edited May 23 '17 at 12:10
Community♦
11
11
answered Oct 25 '08 at 15:02
Konrad RudolphKonrad Rudolph
398k1017871034
398k1017871034
add a comment |
add a comment |
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
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
add a comment |
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
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
add a comment |
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
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
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
add a comment |
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
add a comment |
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.
14
Update: Recent Firefoxes have a stableArray.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
add a comment |
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.
14
Update: Recent Firefoxes have a stableArray.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
add a comment |
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.
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.
answered Oct 24 '08 at 18:34
Steve
14
Update: Recent Firefoxes have a stableArray.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
add a comment |
14
Update: Recent Firefoxes have a stableArray.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
add a comment |
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.
add a comment |
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.
add a comment |
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.
After some more research, it appears, for Mozilla/Firefox, that Array.sort() uses mergesort. See the code here.
edited Jul 24 '16 at 1:17
Genzume
3,12511425
3,12511425
answered Oct 24 '08 at 18:42
latortugalatortuga
1,1512814
1,1512814
add a comment |
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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
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
add a comment |
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
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
answered Dec 21 '18 at 1:15
BorisBoris
1,31511427
1,31511427
add a comment |
add a comment |
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