Skip to content

Instantly share code, notes, and snippets.

@scriptonian
Created December 16, 2017 20:05
Show Gist options
  • Save scriptonian/0db52480af0092a7de3c00f18a28dd56 to your computer and use it in GitHub Desktop.
Save scriptonian/0db52480af0092a7de3c00f18a28dd56 to your computer and use it in GitHub Desktop.
Javascript merge sort
function ScriptoniteSort() {
this.arr = [];
}
ScriptoniteSort.prototype = {
/*
other code goes here
*/
//split the datalist recursively
mergeSplit: function(datalist) {
if (datalist.length === 1) return datalist;
var dataLength = datalist.length,
middle = Math.floor(dataLength / 2),
leftArray = datalist.slice(0, middle),
rightArray = datalist.slice(middle);
return this.merge(this.mergeSplit(leftArray), this.mergeSplit(rightArray));
},
//take two datalists and merge them into one sorted list
merge: function(left, right){
//store sorted result here
var results = [];
while(left.length && right.length) {
var currentMin;
//we compare the two arrays and strip out the minimum of first items
if(left[0] < right[0]) {
currentMin = left.shift();
} else {
currentMin = right.shift();
}
results.push(currentMin);
}
if(left.length) {
results = results.concat(left);
} else {
results = results.concat(right);
}
//return the entire array to caller
return results;
},
mergeSort: function(datalist) {
//store the results
var results = this.mergeSplit(datalist);
console.log("----> " + results);
}
};
var myArr = [9, 11, 5, 1, 7, 2, 15, 1, 8, 6];
//var myArr = [1, 7, 4, 0, 5, 3];
//var myArr = [64, 25, 12, 22, 11];
var collection = new ScriptoniteSort();
collection.mergeSort(myArr);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment