Mergesort in JavaScript

gistfile1.js

/**
 * An implementation for Mergesort. Less efficient
 * than Quicksort. Again, you'd just use Array.sort
 * but if you found yourself unable to use that
 * there's always this option.
 *
 * Tests with:
 *
 * var array = [];
 * for(var i = 0; i < 20; i++) {
 *   array.push(Math.round(Math.random() * 100));
 * }
 *
 * Mergesort.sort(array);
 *
 * @author Paul Lewis
 */
var Mergesort = (function() {

  /**
   * Sorts the array by breaking it down
   * into smaller chunks.
   *
   * @param {Array} array The array to sort
   */
  function sort(array) {

    var length = array.length,
        mid    = Math.floor(length * 0.5),
        left   = array.slice(0, mid),
        right  = array.slice(mid, length);

    if(length === 1) {
      return array;
    }

    return merge(sort(left), sort(right));

  }

  /**
   * Merges two sublists back together.
   * Shift either left or right onto
   * the result depending on which is
   * lower (assuming both exist), and simply
   * pushes on a list if the other doesn't
   * exist.
   *
   * @param {Array} left The left hand sublist
   * @param {Array} right The right hand sublist
   */
  function merge(left, right) {

    var result = [];

    while(left.length || right.length) {

      if(left.length && right.length) {

        if(left[0] < right[0]) {
          result.push(left.shift());
        } else {
          result.push(right.shift());
        }

      } else if (left.length) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }

    }

    return result;

  }

  return {
    sort: sort
  };

})();

Do you know, that ".shift()" and accessing array out of bound may kill performance?

for posterity's sake: you don't need to check for array for length of zero. Just return early if length === 1, so you won't have to divide the array anymore.

There is also a performance bug here, where you incurring cost by creating a lot of sub arrays during the recursion. It would be better to just create an aux array and pass that around.

This implementation uses var result = []; Does this mean it is using more memory than it needs to? (Sorry i'm a little late into the discussion).

Edited: Actually, I take that back I don't know what I'm talking about ><.

I tested out your code for sort a large element array n= 200000, that shift() sure kill performance.

Here is better implementation of merging / conquering:

` var conquer = function(left, right) {
var sorted = [];
var i = 0; //left tracker
var j = 0; //right tracker

while (i < left.length || j < right.length) {
  if (i < left.length && j < right.length){
    if (left[i] < right[j]){
      sorted.push(left[i]);
      i++;
    }else{
      sorted.push(right[j]);
      j++
    }
  }else if (i < left.length){
    sorted.push(left[i]);
    i++;
  }else{
    sorted.push(right[j]);
    j++;
  }
}

return sorted;

} `

what is line 78-80 for?