I was writing a JavaScript implementation of merge sort in NodeJS, since the native V8 sort
function uses quick sort, which is less efficient than merge sort in its worst case. In order to the test the performance, I made an array of 10000 elements, pre-sorted (worst-case for quick sort) and timed how long it took to sort this list with both functions. In a single execution, the native sort
function takes about 16 milliseconds, where my implementation takes about 9 milliseconds. However, when executing both 100 times, the native sort
takes about 2.1 milliseconds on average, and mine takes about 4.3 milliseconds. Here is my code:
const { performance } = require('perf_hooks');
function merge(a, b, func) {
const array = new Array(a.length + b.length);
let aIndex = 0;
let bIndex = 0;
while(aIndex + bIndex < array.length) {
if(aIndex >= a.length || func(a[aIndex], b[bIndex]) > 0) {
array[aIndex + bIndex] = b[bIndex++];
} else {
array[aIndex + bIndex] = a[aIndex++];
}
}
return array;
}
function mergeSort(list, func) {
if(list.length <= 1) {
return list;
}
const half = list.length / 2;
return merge(mergeSort(list.slice(0, half), func), mergeSort(list.slice(half), func), func);
}
function time(func, iters) {
let sum = 0;
for(let i = 0; i < iters; i++) {
let startTime = performance.now();
func();
sum += performance.now() - startTime;
}
return sum / iters;
}
const arr = [...Array(10000).keys()];
const sortFunc = (a, b) => a - b;
console.log("JavaScript built-in sort execution time, one iteration:")
console.log(time(() => arr.sort(sortFunc), 1)); // ~16
console.log("Manually implemented merge sort execution time, one iteration:")
console.log(time(() => mergeSort(arr, sortFunc), 1)); // ~9
console.log();
console.log("JavaScript built-in sort average execution time, 100 iterations:")
console.log(time(() => arr.sort(sortFunc), 100)); // ~2.1
console.log("Manually implemented merge sort average execution time, 100 iterations:")
console.log(time(() => mergeSort(arr, sortFunc), 100)); // ~4.3
Why is it so much faster when executed repeatedly than only once, and why is this improvement more pronounced for the native sort
function?
EDIT: I was able to make my algorithm more efficient by tracking array indices instead of using the slice
method. My code now consistently beats v8's native sort
when used on pre-sorted arrays, but loses on randomized arrays, as expected. Here is that code, for those interested:
const { performance } = require('perf_hooks');
function merge(a, b, func) {
const array = new Array(a.length + b.length);
let aIndex = 0;
let bIndex = 0;
while(aIndex + bIndex < array.length) {
if(aIndex >= a.length || func(a[aIndex], b[bIndex]) > 0) {
array[aIndex + bIndex] = b[bIndex++];
} else {
array[aIndex + bIndex] = a[aIndex++];
}
}
return array;
}
function mergeSortRec(list, func, start, limit) {
if (limit === 1) {
return [list[start]];
}
const half = limit / 2 | 0;
return merge(mergeSortRec(list, func, start, half), mergeSortRec(list, func, half + start, limit - half), func);
}
function mergeSort(list, func) {
return mergeSortRec(list, func, 0, list.length);
}
function time(func) {
let startTime = performance.now();
func();
return performance.now() - startTime;
}
const sortFunc = (a, b) => a - b;
console.log();
console.log("--- Sequential array ---");
console.log();
const sequenceArr = [...Array(10000).keys()];
console.log("JavaScript built-in sort execution time, one iteration:");
console.log(time(() => sequenceArr.slice(0).sort(sortFunc)));
console.log("Manually implemented merge sort execution time, one iteration:");
console.log(time(() => mergeSort(sequenceArr, sortFunc)));
let sum = 0;
for(let i = 0; i < 100; i++) {
const array = sequenceArr.slice(0);
sum += time(() => array.sort(sortFunc));
}
console.log("JavaScript built-in sort average execution time, 100 iterations:");
console.log(sum / 100);
sum = 0;
for(let i = 0; i < 100; i++) {
sum += time(() => mergeSort(sequenceArr, sortFunc))
}
console.log("Manually implemented merge sort average execution time, 100 iterations:");
console.log(sum / 100);
console.log();
console.log("--- Randomized array ---");
console.log();
const randomArrays = new Array(101);
for(let i = 0; i < 101; i++) {
randomArrays[i] = new Array(10000);
for(let j = 0; j < 10000; j++) {
randomArrays[i][j] = Math.random() * 5000 | 0;
}
}
console.log("JavaScript built-in sort execution time, one iteration:");
console.log(time(() => randomArrays[100].slice(0).sort(sortFunc)));
console.log("Manually implemented merge sort execution time, one iteration:");
console.log(time(() => mergeSort(randomArrays[100], sortFunc)));
sum = 0;
for(let i = 0; i < 100; i++) {
const array = randomArrays[i].slice(0)
sum += time(() => array.sort(sortFunc));
}
console.log("JavaScript built-in sort average execution time, 100 iterations:");
console.log(sum / 100);
sum = 0;
for(let i = 0; i < 100; i++) {
sum += time(() => mergeSort(randomArrays[i], sortFunc))
}
console.log("Manually implemented merge sort average execution time, 100 iterations:");
console.log(sum / 100);