# 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. – rolfl Aug 10 '14 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. – Schism Aug 14 '14 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. – Flambino Aug 10 '14 at 17:51
• The comparison function is like that to mirror the comparison function to be provided to native sort(), I think. – Schism Aug 14 '14 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. – janos Aug 14 '14 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). – Schism Aug 14 '14 at 21:20