Array.prototype.sort(compareFn) works different in browsers?

Question

I've been testing the compare function given as callback to the Array.prototype.sort(compareFn) when the compareFn 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?

Answer 1

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