Why does Array.sort compare certain value pairs twice sometimes?

Question

I'm using this Javascript code to view the order in which array elements are compared when the sort method is invoked.

function log(text)
{
    document.documentElement.appendChild(document.createElement('div')).appendChild(document.createTextNode(text));
}

[5, 4, 3, 2, 1].sort(function (a, b) {
    log("comparing " + a + " and " + b);
    return a - b;
});

I'm not surprised to see that different browsers produce different outputs because of diverse implementations. What I cannot realize is why IE and Opera sometimes compare the same pair of values twice in succession. That doesn't make any sense to me. Sorting arrays looks like such a basic language feature I'm probably missing something here. Can someone explain this behavior?

Here are my test results:

IE 9 and 10

• comparing 4 and 5
• comparing 4 and 5
• comparing 3 and 5
• comparing 3 and 4
• comparing 2 and 5
• comparing 2 and 4
• comparing 2 and 3
• comparing 1 and 5
• comparing 1 and 3
• comparing 1 and 2

Firefox

• comparing 5 and 4
• comparing 5 and 3
• comparing 4 and 3
• comparing 2 and 1
• comparing 5 and 1
• comparing 3 and 1
• comparing 3 and 2

Chrome

• comparing 5 and 4
• comparing 5 and 3
• comparing 4 and 3
• comparing 5 and 2
• comparing 4 and 2
• comparing 3 and 2
• comparing 5 and 1
• comparing 4 and 1
• comparing 3 and 1
• comparing 2 and 1

Opera

• comparing 5 and 4
• comparing 2 and 1
• comparing 3 and 1
• comparing 3 and 1
• comparing 3 and 2
• comparing 5 and 1
• comparing 4 and 1
• comparing 4 and 2
• comparing 4 and 3

And the proof of concept: http://jsfiddle.net/Sd9ph/

Answer 1

We don't know the details, since their implementations are not open source.

Yet, Opera seems to use some a merge sort where the merge phase includes comparing the range boundaries (to do a more efficient concatenation instead of merging item-per-item - when possible). In the minimal case, one of the ranges has only one item in it - which will then be compared twice if it cannot just be prepended. It could use an optimisation, but it won't happen that often, so it wasn't worth it apparently.

You can check the behaviour here with three-item-arrays. Example for [3,2,1]:

3 2 1

[3][2 1] // divide

[3][2 1] // compare (and exchange)
    ^ ^
[3][1 2] // compare upper with lower boundary (would concat if possible)
  ^^
[3][1 2] // but they're overlapping, so let's merge…
 ^  ^
1 [3][2] // …by comparing smallest items from each set
   ^  ^
1 2 3

Example for [2,1,4,3], with concatenation:

2 1 4 3

[2 1][4 3] // divide

[2 1][4 3] // and sort sub-arrays
 ^ ^  ^ ^
[1 2][3 4] // compare boundaries
    ^^
1 2 3 4    // uh, we're done already!

This concatenation will make the mergesort faster for (at least partly) already-sorted arrays.

Internet Explorer in contrast does a classical insertion sort. I'd assume that it first tests whether the array is already sorted - which fails at the first comparison, 4 is not >= 5. Then it inserts 4 before 5, 3 before 5 and 4, 2 before 5 and 4 and 3, and since 1 lacks a comparison with 4 it seems it uses a kind of binary search for that.