0
\$\begingroup\$

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 = [];
  // merge adjacent;
  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];
}
\$\endgroup\$
2
\$\begingroup\$

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.

Your code.

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.

\$\endgroup\$
  • \$\begingroup\$ 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]] ? \$\endgroup\$ – Kevin T. Feb 23 '18 at 19:56
  • \$\begingroup\$ @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 \$\endgroup\$ – Blindman67 Feb 23 '18 at 20:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin T. Feb 23 '18 at 21:06
  • \$\begingroup\$ @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. \$\endgroup\$ – Blindman67 Feb 23 '18 at 21:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin T. Feb 23 '18 at 22:12

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.