Skip to content

Instantly share code, notes, and snippets.

@paullewis
Created March 5, 2012 23:44
Show Gist options
  • Save paullewis/1982121 to your computer and use it in GitHub Desktop.
Save paullewis/1982121 to your computer and use it in GitHub Desktop.
Mergesort in JavaScript
/**
* 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
};
})();
@emurillo510
Copy link

emurillo510 commented Oct 20, 2016

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 ><.

@Moonhint
Copy link

Moonhint commented Feb 28, 2017

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;

} `

@robinchoii
Copy link

what is line 78-80 for?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment