# Merge sort in JavaScript

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)

• 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. Aug 10, 2014 at 16:12
• 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. Aug 14, 2014 at 21:25

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;
}

• 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. Aug 10, 2014 at 17:51
• The comparison function is like that to mirror the comparison function to be provided to native sort(), I think. Aug 14, 2014 at 21:21
• @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. Aug 14, 2014 at 21:26

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;
}
}
}
}

• 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). Aug 14, 2014 at 21:20