Skip to content

Instantly share code, notes, and snippets.

@swapnilshrikhande
Created October 18, 2014 15:41
Show Gist options
  • Save swapnilshrikhande/d38da90666f3081af6e1 to your computer and use it in GitHub Desktop.
Save swapnilshrikhande/d38da90666f3081af6e1 to your computer and use it in GitHub Desktop.
javascript merge sort utility
//Developed by Swapnil Shrikhande
//USAGE
//utils.sort.mergesort([8, 5, 3, 53, 6, 2, 4, 9, 445, 689, 2774, 328, 193, 482],[comparator_function]);
var utils = utils || {};
utils.sort = utils.sort || {};
utils.sort.mergesort = function(list, comparator) {
if (list.length == 1) {
return list;
}
var leftSorted = utils.sort.mergesort(list.slice(0, list.length / 2), comparator);
var rightSorted = utils.sort.mergesort(list.slice(list.length / 2, list.length), comparator);
return utils.sort.merge(leftSorted, rightSorted, comparator);
};
utils.sort.merge = function(left, right, comparator) {
var sorted = [];
var totalLength = left.length + right.length;
var leftIndex = 0;
var rightIndex = 0;
for (var index = 0; index < totalLength; index++) {
if (leftIndex < left.length && rightIndex < right.length) {
var compareBool = comparator ? comparator(left[leftIndex], right[rightIndex])
: left[leftIndex] < right[rightIndex];
if (compareBool) {
sorted[index] = left[leftIndex++];
} else {
sorted[index] = right[rightIndex++];
}
} else if (leftIndex < left.length) {
sorted[index] = left[leftIndex++];
} else if (rightIndex < right.length) {
sorted[index] = right[rightIndex++];
}
}
return sorted;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment