This is also fast in Safari because the array isn't sparse enough for JavaScriptCore to send it down the fallback path.

EDIT: In order to go down the fallback path the array needs to be both sufficiently large and sufficiently sparse (< 12.5% occupied). You can see the difference in algorithms by modifying your test case like so:

Dense, fast path:

    var a = [];
    for (var i = 1; i < 4e6; i++)
      a[i * 5] = i.toString();
    a.sort();

Sparse, fallback path:

    var a = [];
    for (var i = 1; i < 4e6; i++)
      a[i * 10] = i.toString();
    a.sort();

By my count, it's very sparse - only 0.003% occupied. I suppose the initial size declaration could make it dense, but then it would use a considerable amount of (virtual?) memory. Unfortunately, I don't have access to Safari to test that.

Hmm… it looks like I misspoke. The "sparse mode" check that Array.prototype.sort performs in JavaScriptCore appears to be different than the its concept of sparse array storage, which is used under the conditions I described. The "sparse mode" check in the sorting code appears to be related to whether the array instance has getters/setters or properties defined via Object.defineProperty. The performance difference my code demonstrates is due to the extra overhead of iterating the sparse array storage compared to a vector, and not due to the different sorting algorithms that are employed.