Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Array.sort stability in different browsers

Tags:

javascript

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")
like image 478
georg Avatar asked May 10 '13 09:05

georg


People also ask

Is array sort stable?

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).

Which is the most stable sorting method?

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.

What is the best way to sort an array?

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.

How do you make a comparison sort stable?

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.


1 Answers

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

like image 169
12 revs, 9 users 38% Avatar answered Nov 25 '22 23:11

12 revs, 9 users 38%