javascript - Array.prototype.sort(compareFn) works different in browsers? - Stack Overflow

admin管理员组

文章数量:1295743

I've been testing the pare function given as callback to the Array.prototype.sort(pareFn) when the pareFn returns value = 0, but i get a unexpected behaviour in Chrome:

/* Chrome */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;})
//WUT? returns [6, 1, 3, 4, 5, 2, 7, 8, 9, 10, 11]

/* Firefox */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;});
//Work's fine: returns [1,2,3,4,5,6,7,8,9,10,11]

Anybody knows what happen this?

I've been testing the pare function given as callback to the Array.prototype.sort(pareFn) when the pareFn returns value = 0, but i get a unexpected behaviour in Chrome:

/* Chrome */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;})
//WUT? returns [6, 1, 3, 4, 5, 2, 7, 8, 9, 10, 11]

/* Firefox */
[1,2,3,4,5,6,7,8,9,10].sort(function(){return 0;});
//returns [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10,11].sort(function(){return 0;});
//Work's fine: returns [1,2,3,4,5,6,7,8,9,10,11]

Anybody knows what happen this?

• javascript
• arrays
• sorting

Share Follow asked May 18, 2017 at 20:17 Gonzalo Pincheira ArancibiaGonzalo Pincheira Arancibia 3,62322 gold badges2525 silver badges4343 bronze badges 6

• By returning 0 from the function, you're saying all of the values are equal, so it sorts them randomly, apparently. – Heretic Monkey Commented May 18, 2017 at 20:19
• 2 Chrome's sorting algorithm is not stable. – elclanrs Commented May 18, 2017 at 20:22
• @elclanrs what does mean algorithm is not stable? – Gonzalo Pincheira Arancibia Commented May 18, 2017 at 20:50
• 1 @GonzaloPincheiraArancibia That it won't preserve the order of items which your parison function deems equal (i.e. in your case, all of them). – Bergi Commented May 18, 2017 at 21:43
• See also Weird behavior in sorting JavaScript array [duplicate] – ephemient Commented May 21, 2017 at 4:45

 |  Show 1 more ment

1 Answer 1

Sorted by: Reset to default 12 +50

I get unexpected behaviour in Chrome. Anybody know what happens?

Actually, this is not unexpected. It appears that your Firefox browser version implements stable sorting, whereas your Chrome browser version does not. Browsers are not required to adopt a stable sorting algorithm (and may choose performance over stability).

A stable sorting algorithm returns equal list items in the same order as they appear originally, whereas an unstable sorting algorithm does not.

Stable and unstable sorting

Consider the following example, where a list of 11 men is sorted according to their age. The sorting algorithm sees 9 men of the same age (45 years old), one younger (39 years old), and one older (52 years old). After sorting, the youngest one (Mike) appears first in the list, then the 9 of the same age may appear in any order, and then the oldest one (Liam) at the end.

console.log([
    {name: 'John', age: 45},
    {name: 'Pete', age: 45},
    {name: 'Matt', age: 45},
    {name: 'Liam', age: 52},
    {name: 'Jack', age: 45},
    {name: 'Will', age: 45},
    {name: 'Zach', age: 45},
    {name: 'Josh', age: 45},
    {name: 'Ryan', age: 45},
    {name: 'Mike', age: 39},
    {name: 'Luke', age: 45}
  ].sort(function(a, b){
    // sort by ascending age
    return a.age - b.age;
  }).map(function(i){
    // get a sorted list of names
    return i.name;
  }).join(', ')
);

When I run this in Chrome, I get

Mike, Will, Matt, John, Jack, Pete, Zach, Josh, Ryan, Luke, Liam

which clearly represents an unstable sort. A stable sort would have returned

Mike, John, Pete, Matt, Jack, Will, Zach, Josh, Ryan, Luke, Liam

However, to a sorting algorithm, both lists are identical when representing age, which is what the sorting algoritm was told to:

39, 45, 45, 45, 45, 45, 45, 45, 45, 45, 52

Browser differences

In your code example, you tell the sorting algorithm that all list items are equal (by returning 0 from the parison function). An unstable sorting algorithm may then sort these items in any order (as Chrome does when there are 11 items in the list), whereas a stable sorting algorithm will sort equal items in original order (as Firefox does).

In your example of sorting in Chrome, there is a difference between the array with 10 items (which appears to be sorted with a stable algorithm) and the array with 11 items. It is known that Chrome uses Insertion sort (stable) for small arrays (<= 10 items), and a Quicksort variant (unstable) for larger arrays.

For more info on how sorting algorithms works and sorting stability, check out Wikipedia on sorting algorithms, this previous SO question or this page with animated illustrations of various sorting algorithms.

本文标签： javascriptArrayprototypesort(compareFn) works different in browsersStack Overflow