Mergesort implementation, eliminating slice()

I am having trouble coming up an alternate solution to my mergesort. I think using slice is an expensive operation. I have two implementations, recursive and iterative.

function mergeSortRecursive(arr) {
// base case
if (arr.length <= 1) {
return arr;
}

var leftArr =  arr.slice(0, arr.length/2);
var rightArr = arr.slice(arr.length/2);
var leftSorted = mergeSortRecursive(leftArr);
var rightSorted = mergeSortRecursive(rightArr);
// merge subarrays
return merge(leftSorted, rightSorted);
}

mergeSortRecursive([1,4,5,245,7, 3,3,6,31]);

function merge(left, right) {
var result = [];
var indexLeft = 0;
var indexRight = 0;
// while result is not fully populated
while(result.length < (left.length + right.length)) {
// if all elements in left have been added, then add remaining
right elements
if (indexLeft === left.length) {
result = result.concat(right.slice(indexRight));
}
// if all elements in right have been added, then add remaining left elements
else if (indexRight === right.length) {
result = result.concat(left.slice(indexLeft));
}
// compare elements in subarrays and add lower of the two to result
else if (left[indexLeft] <= right[indexRight]) {
result.push(left[indexLeft++]);
} else {
result.push(right[indexRight++]);
}
}
return result;
}

function mergeSortIterative(arr) {
// create an array of subarrays with each element
var splitArr = arr.map(function(element) {
return [element];
});
// while there is more than one subarray
while (splitArr.length > 1) {
var result = [];
for (var i = 0; i < splitArr.length; i+=2) {
// for pairs merge
if (splitArr[i + 1]) result.push(merge(splitArr[i],
splitArr[i+1]));
// for last odd element, just add to results
else result.push(splitArr[i]);
}
// overwrite old splitArr
splitArr = result;
}
return splitArr[0];
}


Alternative ?

Not to sure what you mean by alternative solution. A merge sort is a merge sort and you need to create arrays, via slice, manually, or even creating a buffer and managing virtual arrays will all incur some overhead.

If you want to improve performance then there is plenty of room for an improved alternative to your code.

Your recursive function is inherently a poor performer but it outperforms the iterative function because the iterative function does not use a stack to optimize data processing.

Your merge function is somewhat sloppy and can be improved, it is the core of the functionality of the sort. You gain the greatest benefit via improvements in the merge function. Even greater improvement if you can side step the need to call it as often.

Recursion, a glorified stack.

In Javascript recursive code has a large overhead. Each call creates a new context that is pushed to the heap. You also can never know how deep you are in the call stack, so a recursive function is always at risk of a call stack overflow.

Recursion is in reality just a way to implement a stack. Each recursion pushes the current execution state to the stack and create the new one. Each return disposes the current state and pop the previous one of the top of the stack.

Many people forget this when writing recursive code, and don't realize that the state stack can many times be more efficiently implemented as a simple stack using a JavaScript array.

Another very common mistake in recursive code is the exit condition. Stepping into a function is expensive and should be avoided.

Annotated your code to show what I mean

function mergeSortRecursive(arr) {

// the exit from recursion one step too deep
if (arr.length <= 1) {
return arr;
}

var leftArr =  arr.slice(0, arr.length/2);
var rightArr = arr.slice(arr.length/2);

// You know at this point if both recursions are going exit early
// because the array lengths are <= 1. You should just skip the
// recursion here rather than inside the next two calls
var leftSorted = mergeSortRecursive(leftArr);
var rightSorted = mergeSortRecursive(rightArr);

return merge(leftSorted, rightSorted);
}


The merge function

Inside the while loop of the merge function you are doing too much. Each 2 values that need to be compared have the overhead of two if statements. They are true only when the loop is ready to exit. The loop should only deal with the comparison of two values and after the loop you can clean up by adding the remaining array content to the result.

Improving the merge

Remove the unneeded if statements and put them after the loop.

function merge(left, right) {
const result = [];
while (left.length && right.length) {
result.push((left[0] <= right[0] ? left : right).shift());
}

if(left.length + right.length){
result.push(...(left.length > 0 ? left : right));
}
return result;
}


Side step merge.

I you inspect the running of the code and the array sizes that merge merges you will notice that 50% of the merges are of two arrays each of length 1. In effect you are using the complicated merge function to sort two numbers.

You can side step the merge function for array sizes 1 with the following

The recursive modification

function mergeSort(arr) {
var len = arr.length / 2;
if (len < 1) { return arr }

// the following avoids stepping one too deep into the recursion as well
if (len === 1) { // if array sizes 1 then skip the merge
return arr[0] < arr[1] ? [arr[0], arr[1]] : [arr[1],arr[0]];
}

return merge(mergeSort(arr.slice(0, len)), mergeSort(arr.slice(len)));
}


For the iterative function you can map pre-merged values

var split = [];;
for(var i = 0; i < arr.length-1; i+= 2){
split.push(arr[i] < arr[i+1] ? [arr[i],arr[i+1]] : [arr[i+1],arr[i]] )
}
if(arr.length % 2) { splitArr.push([arr[arr.length -1]]) }


Implementing an iterative stack.

If you count the number of times you need to compare 2 values the recursive function does about 10% less than the iterative function. But that can be changed by making the iterative function act like a recursive function.

The splitArr replaces the call stack and heap, and holds the merged arrays. When there are no more items to merge in splitArr the job is complete.

Note turns out a queue is quicker than a stack in this case but the idea is the same

function mergeSortIterative(arr) {
const stack = [];
for (var i = 0; i < arr.length - 1; i+= 2) {
const ii = i + 1;
stack.push(arr[i] < arr[ii] ? [arr[i], arr[ii]] : [arr[ii], arr[i]] )
}
if (arr.length % 2) { stack.push([arr[arr.length -1]]) }

// the loop replaces the recursive function
while (stack.length > 1){
stack.push(merge(stack.shift(), stack.shift()));
}
return stack[0];
}


Now you have an alternative solution without a slice in sight, improved memory and CPU use because you can avoid the recursive over head, and a reduction in the overall complexity by turning many of the merge call into simpler single statement sort.

• Im not understanding the syntax in the if statement of mergeSort(). If (len === 1) why do return an array with two values, either [arr[0], arr[1] : [arr[1], arr[0]] ? Feb 23, 2018 at 19:56
• @KevinT. They are pre sorted arrays (of two items) for the merge function. The merge function is not very efficient when you pass it arrays of size 1, pre sorting small array reduces the work load Feb 23, 2018 at 20:48
• So I'm clear, we do this, passing in a presorted array of two items, even though we really just have one real item in the array, to make it more efficient for the merge function. I'm still stepping through it line by line with a debugger; statement. Feb 23, 2018 at 21:06
• @KevinT. If the number of Items is 100 this step saves 25 calls to merge and 50 calls to mergeSort by doing what the line return merge(mergeSort(arr.slice(0, len)), mergeSort(arr.slice(len))); would otherwise do. Feb 23, 2018 at 21:22
• I am trying to grasp how you calculated the amount of savings your code is creating, "saving 25 calls to merge", "50% of the merges are of size 1". I'm looking thought Algorithms by Sedgewick and I am not finding the practical methods of calculating these savings other than the standard proofs. Can you point me to some resources to figure this out? Am I not using devtools fully? Understanding these code savings will help me understand the code more thoroughly and HOW exactly performance is gained for this and other algos. AS of now I literally walk out small examples by hand. Feb 23, 2018 at 22:12