Skip to content

Instantly share code, notes, and snippets.

@Anaerin
Last active June 11, 2021 20:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Anaerin/1fa22d764630f9135e9ed55dee43bddb to your computer and use it in GitHub Desktop.
Save Anaerin/1fa22d764630f9135e9ed55dee43bddb to your computer and use it in GitHub Desktop.
Merge Sort for Javascript
function MergeSort(arrInput) {
// If there's only 1 entry, return it.
if (arrInput.length == 1) return arrInput;
// If there are 2 entries, return them in the right order.
else if (arrInput.length == 2) {
// If the second entry is bigger, return it first
if (arrInput[1] > arrInput[0]) return [arrInput[1], arrInput[0]];
// Otherwise, the first entry is bigger, or they're equal, so return them as-is
else return arrInput;
}
// There's more than 2 entries, time to split the list and recurse
else {
// Find the middle.
let splitPoint = Math.floor(arrInput.length/2);
let leftPart = arrInput.slice(0, splitPoint);
let rightPart = arrInput.slice(splitPoint);
// At this point, we're done with arrInput and can safely remove it.
arrInput = null;
delete arrInput;
// Call ourselves on the two halves
let left = MergeSort(leftPart), right = MergeSort(rightPart);
// Okay, we've got both results, split them out into their parts, make position trackers, and an output array.
let leftPos = 0, rightPos = 0, out = [];
// While we still have values to process
while((leftPos < left.length) && (rightPos < right.length)) {
// If the left-hand side is bigger, push that to the output and move on.
if (left[leftPos] > right[rightPos]) out.push(left[leftPos++]);
// If the right-hand side is bigger, push that to the output and move on.
else if (right[rightPos] > left[leftPos]) out.push(right[rightPos++]);
// Neither side is bigger, therefore they're the same. Push them both and move on.
else if (left[leftPos] == right[rightPos]) {
out.push(left[leftPos++]);
out.push(right[rightPos++]);
}
}
if (leftPos == left.length && rightPos != right.length) {
// We reached the end of the left set. Append the rest of the right set.
out.push(...right.slice(rightPos));
} else if (rightPos == right.length && leftPos != left.length) {
// We reached the end of the right set. Append the rest of the left set.
out.push(...left.slice(leftPos));
}
// return the merged and sorted results array.
return out;
}
}
@Anaerin
Copy link
Author

Anaerin commented Sep 26, 2019

Fun fact, the ++ operator, when used like this, returns the current number THEN increments it. That's what makes the .push(left[leftPos++]) and .push(right[rightPos++]) work.
The .push(...right.slice(rightPos)) is using the spread operator for extra smoothness and speed.

This is slow, compared to the native .sort() function, but I would never be able to compete with that anyway. This is a fun proof-of-concept and learning tool, to teach something better than the standard Bubble Sort, along with recursion and async operations in JS.

@Anaerin
Copy link
Author

Anaerin commented Jun 11, 2021

Updated so it isn't asynchronous anymore, makes it noticably faster (though it shouldn't) because JS' async functionality is still single-threaded, so the overhead makes it bad.

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