Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
};
})();
@joelarson4

This comment has been minimized.

Copy link

commented Feb 26, 2013

shouldn't you check for null or zero length array in sort()?

@hyeomans

This comment has been minimized.

Copy link

commented Sep 11, 2013

On line 31:
if( array.length == 0 || array.length == 1) { ...

@Yaffle

This comment has been minimized.

Copy link

commented Nov 28, 2013

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

@chtrinh

This comment has been minimized.

Copy link

commented Feb 25, 2016

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.

@emurillo510

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

commented Dec 15, 2017

what is line 78-80 for?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.