JavaScript, sorting with second parameter is faster

Question

I have made a little test, and found out that array.sort(function(a, b) { return a - b; }); is a lot faster than array.sort(); in JavaScript.

The results were quite shocking, about 1.7 times faster in IE9, 1.6 times in FF7 and 6.7 times in Chrome.

Also, by implementing quicksort by myself in JS, I found it was even faster than both methods mentioned above. (Two different implementations, one accepts a comparer function as a parameter, the other doesn't. Both were faster.)

Is there any reasonable explanation?

EDIT: My implementations:

No comparer:

function quickSort(array, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }

    if(to - from < 1) {
        return;
    }

    var i = from, pivot = to, t;

    while(i < pivot) {
        if(array[i] > array[pivot]) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }

    quickSort(array, from, pivot - 1);
    quickSort(array, pivot + 1, to);
}

With comparer:

function quickSortFunc(array, sortfunc, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }

    if(to - from < 1) {
        return;
    }

    var i = from, pivot = to, t;

    while(i < pivot) {
        if(sortfunc(array[i], array[pivot]) > 0) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }

    quickSortFunc(array, sortfunc, from, pivot - 1);
    quickSortFunc(array, sortfunc, pivot + 1, to);
}

It's a possibility that the sort function is run from averages. How big were the arrays that you used? — Matt, Aug 28 '11 at 12:53
"Normal" sort works on the string representation of the elements. That could be a possible overhead. — Felix Kling, Aug 28 '11 at 12:54
Matt, I tested it on arrays of 100, 1000, 10000 and 100000 elements. Felix, I though about that two, it still doesn't explain why my implementation with a comparer was faster than the native implementation with a comparer. — Shay Ben Moshe, Aug 28 '11 at 12:57
Here is a jsPerf as a start: http://jsperf.com/sort-comparison *Edit:* Fixed some errors (I think). — Felix Kling, Aug 28 '11 at 12:59
I think to give a proper answer it would help if we knew your implementation. — Felix Kling, Aug 28 '11 at 13:09
Yep, Felix looks correct. In your implementation `(array[i] > array[pivot])` will compare ints instead of strings. — Douglas, Aug 28 '11 at 13:21

score 1 · Answer 1 · edited May 23 '17 at 10:30

There's two factors that come into play:

First, as Felix King mentioned in the comments, the native sort method converts each array member to a string before comparing. Using function(a, b) { return a - b; } is way faster if all (or most) array members are numbers.

Second, the sorting algorithm is implementation dependent. As you may or may not know, quicksort performs really bad if you insert a new element into an already sorted array. Maybe that's why WebKit decided to implement Selection Sort instead.

But fear not, help is near! Somebody already forked WebKit to fix this

score 0 · Answer 2 · answered Aug 28 '11 at 16:51

Many reasons would come into play. Not having to check variable type is one of them and only one of them. And your implementation makes the optimiser happy. It works with dense array, it works only with numbers, the variables are well scoped and reused. No this, no with, no eval, no magic variables, properties, functions, or types. It would optimise well.

However, if you have tried to implement type-idependent, order-independent array methods such as reverse() you may also find that your own implementation is faster. At least mine is.

Why?

JavaScript is heavily optimised nowadays, espcially on loops and repeated operations on same type of stuffs - number, string, even objects of same shape (it's complicated). In extreme cases the runtime would inline your functions, would skip variable type checks, and, in case of Chrome, would even keep your numbers in registries so that your loop can be as fast as C.

Wow.

But these optimisations only took off in recent years. At this moment, native functions are not yet as optimisable as user code. They don't undergo as much dynamic optimisations as user code do.

There, I said it.

Currently, user code may run faster then native implementation, espcially since the programmer knows what data flow in it. But this can be temporary.

I'll stop here and let you decide whether you want to create your own array library. ;)

That's only part of the truth. Note that most Array methods are intentionally defined to be generic, so they must work on objects that are not arrays. If your implementation is faster, it's probably because you forgot some crazy special case. For example `Array.prototype.reverse.call({'2':'2','3':'3',length:'3.5',apples:'oranges'})` or even `var a=[];a[1]=1;a.reverse().hasOwnProperty(1)//false`. These are things that browser vendors must not optimize. Otherwise jQuery will have to work on another ticket ;) — user123444555621, Aug 28 '11 at 19:43
@Pumbaa80: Just checked the spec, but failed to see what's extreme about the example. The spec says take the length, make it unsigned int, then start reversing from 0 to length-1. May I know what is the pitfall here? — Sheepy, Aug 29 '11 at 01:28
I haven't seen your implementation, but [mine (considering special cases)](http://jsperf.com/array-reverse) is definitely slower. — user123444555621, Aug 29 '11 at 13:49

score 0 · Answer 3 · answered Aug 31 '11 at 15:06

This is quite a wild guess, but could the performance hit occur due to the native sort, checking if the attributes passed is blank or null... Hence searching up the default function on each search (instead of once)...

It could be a mistaken optimization issue, that could be resolved if true... Hopefully someone in firefox dev can answer this :)

JavaScript, sorting with second parameter is faster

3 Answers3