7
\$\begingroup\$

I implemented this merge sort in JS and noticed that for random integer numbers it's a lot faster than the build in sort functions of all the browsers I tested (Chrome, FF, IE). Does anyone have an idea why that is? Also, is there a way to make my code even faster?

function bubbleSort(f, a, start, end) {
    end--;
    while(end > start) {
        for(var i = start; i < end; i++) {
            var x = a[i], y = a[i+1];
            if(f(x, y) > 0) {a[i] = y; a[i+1] = x;}
        }
        end--;
    }
}

function merge(f, a, start, a2, start2, mid, end) {
    var i = start, i1 = start2, i2 = mid;
    while(i1 < mid && i2 < end) {
        if(f(a2[i1], a2[i2]) <= 0) a[i++] = a2[i1++];
        else a[i++] = a2[i2++];
    }
    if(i1 >= mid) {
        i1 = i2;
        mid = end;
    }
    while(i1 < mid) {
        a[i++] = a2[i1++];
    }
};

function _mergeSort(f, a1, a2, start, end) {
    var mid;
    if(end - start < 2) return;
    if(end - start < 8) { bubbleSort(f, a1, start, end); return; }
    mid = Math.floor((start + end)/2);
    _mergeSort(f, a2, a1, start, mid);
    _mergeSort(f, a2, a1, mid, end);
    merge(f, a1, start, a2, start, mid, end);
};

function mergeSort(f, a) {
    var a2 = a.slice();
    _mergeSort(f, a, a2, 0, a.length);
};

Here is some JSFiddle site to test the code http://jsfiddle.net/mxbppLu0/ In Chrome I get the biggest difference (1.4 vs. 3 seconds for 10 million numbers)

\$\endgroup\$
  • \$\begingroup\$ Consider using an insertion sort instead of the bubble-sort. The TimSort is well studied, and implemented first in Python, then Java, is well known, and uses merge+insertion. \$\endgroup\$ – rolfl Aug 10 '14 at 16:12
  • \$\begingroup\$ Another alternative to bubble sort is the fascinating comb sort. Wikipedia gives 1.3 as an example gap distance, and I've found it to be pretty good. \$\endgroup\$ – Schism Aug 14 '14 at 21:25
4
\$\begingroup\$

You define the comparison function like this:

function(a, b) { return a - b }

and then you use it like this:

if (f(x, y) <= 0) { ... }
if (f(x, y) > 0) { ... }

This is a bit tedious. It would be more intuitive like this:

function(a, b) { return a <= b }

and use it like this:

if (f(x, y)) { ... }
if (!f(x, y)) { ... }

Why is it faster?

I don't know, but as @Flambino commented:

I browsed around the V8 source code and the sort function does a lot of stuff, namely handling sorting of non-array objects, arrays with "holes", and similar cases. All of that before actually sorting anything. I have no idea what exactly is causing the slowdown, but, as mentioned, there's just a lot of stuff going on there. Their implementation is also sorting in-place, which could be a contributing factor. But I honestly haven't dug that deeply

How to make it faster?

Changing the comparison function like this:

function(a, b) { return a < b }

and the bubble sort condition to use 6 instead of 8 (in if (end - start < 6) { ...), together, often yielded faster result in my test runs, but not always, and I don't think that means anything.

The bottom line: I don't know...

Naming and formatting

The code would be more readable if you improved some of the names. For example renaming a and a2 to part1 and part2, respectively. Or even arr1 and arr2. It would make them look more like arrays, instantly.

This may be a matter of taste, but instead of this:

var x = a[i], y = a[i+1];
if(f(x, y) > 0) {a[i] = y; a[i+1] = x;}

I would find this slightly more readable:

var x = a[i];
var y = a[i + 1];
if (f(x, y) > 0) {
    a[i] = y;
    a[i + 1] = x;
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ re Why it's faster. I browsed around the V8 source code and the sort function does a lot of stuff, namely handling sorting of non-array objects, arrays with "holes", and similar cases. All of that before actually sorting anything. I have no idea what exactly is causing the slowdown, but, as mentioned, there's just a lot of stuff going on there. Their implementation is also sorting in-place, which could be a contributing factor. But I honestly haven't dug that deeply. \$\endgroup\$ – Flambino Aug 10 '14 at 17:51
  • 1
    \$\begingroup\$ The comparison function is like that to mirror the comparison function to be provided to native sort(), I think. \$\endgroup\$ – Schism Aug 14 '14 at 21:21
  • \$\begingroup\$ @Schism yup, you're probably right. Interestingly, if you look at that fiddle and make the native method use a <= b, it will be even slower than it is now. \$\endgroup\$ – janos Aug 14 '14 at 21:26
1
\$\begingroup\$

I recognise that you asked about your mergesort, but I couldn't help but notice your bubblesort...

You're doing end-- once before the loop, and again at the end of each iteration. Instead, you could just use --end in your condition. Furthermore, your swapping could be rewritten with just one temporary variable:

function bubbleSort(f, a, start, end) {
    while(--end > start) {
        for(var i = start; i < end; i++) {
            if (f(x, y) > 0) {
                var temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ For extra fun, replace the while condition with the inverse goes to operator (start <-- end), and the swap with a[i] = a[i + 1] + (a[i + 1] = a[i], 0). \$\endgroup\$ – Schism Aug 14 '14 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.