Menu
Array.sort Sorting Stability in Different Browsers
this is an old question, I think it would be helpful if we collect the most recent data here. Please click this fiddle
http://jsfiddle.net/Wrt9R/
and share your results.
Fiddle code:
a = []
for(var i = 0; i < 1000; i++) {
a.push({'key':100 + Math.round(Math.random() * 100), 'val': i + 1000 })
}
a.sort(function(x, y) { return x.key - y.key })
b = []
for(var i = 0; i < 1000; i++) {
b.push(a[i].key * 10000 + a[i].val);
}
c = b.slice(0)
b.sort()
stable = (b.join() === c.join())
document.body.innerHTML = navigator.userAgent.toString() + "<br>" + (stable ? "stable": "UNSTABLE")
478
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).
Several common sorting algorithms are stable by nature, such as Merge Sort, Timsort, Counting Sort, Insertion Sort, and Bubble Sort. Others such as Quicksort, Heapsort and Selection Sort are unstable.
Quicksort. Quicksort is generally thought of as the most efficient 'general' sorting algorithm, where nothing is known about the inputs to the array, and it's more efficient than insertion sort on large lists.
There can be sorting algo specific ways to make it stable, but in general, any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal keys.
Stability Browser OS full UA string unstable Safari 5.3 OS X Lion (10.7.5) Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_5) AppleWebKit/536.29.13 (KHTML, like Gecko) Version/6.0.4 Safari/536.29.13 stable Firefox 15.0.1 OS X Lion Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:15.0) Gecko/20100101 Firefox/15.0.1 unstable Chrome 21 OS X Lion (10.7.5) Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_5) AppleWebKit/537.1 (KHTML, like Gecko) Chrome/21.0.1180.79 Safari/537.1 stable Firefox 16 Win 7 Mozilla/5.0 (Windows NT 6.1; rv:16.0) Gecko/20100101 Firefox/16.0 unstable Chrome 26 Win 7 x64 Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.64 Safari/537.31 unstable IE 9.0 Win 7 x64 Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; WOW64; Trident/5.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; .NET4.0C; InfoPath.3; .NET4.0E) stable Firefox 20 Win 7 x64 Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20100101 Firefox/20.0 unstable IE 10 Win 7 Mozilla/5.0 (compatible; MSIE 10.0; Windows NT 6.1; Trident/6.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; InfoPath.3; .NET4.0C; .NET4.0E) unstable Chrome 26 Win 7 Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.64 Safari/537.31 stable Firefox 20 Win 8 x64 Mozilla/5.0 (Windows NT 6.2; WOW64; rv:20.0) Gecko/20100101 Firefox/20.0 unstable IE 10 Win 8 x64 Mozilla/5.0 (compatible; MSIE 10.0; Windows NT 6.2; WOW64; Trident/6.0; .NET4.0E; .NET4.0C; .NET CLR 3.5.30729; .NET CLR 2.0.50727; .NET CLR 3.0.30729; Tablet PC 2.0) unstable Chrome 26 Win 8 x64 Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.64 Safari/537.31 unstable Opera 12.15 Win 8 x64 Opera/9.80 (Windows NT 6.2; WOW64) Presto/2.12.388 Version/12.15 stable Firefox 20 Ubuntu Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:20.0) Gecko/20100101 Firefox/20.0 unstable Chrome 26 Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.63 Safari/537.31 unstable Chrome 20 Win 7 x64 Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/536.11 (KHTML, like Gecko) Chrome/20.0.1132.57 Safari/536.11 unstable Chrome 28 Win 8 x64 Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.72 Safari/537.36
169
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
