Last active
June 11, 2021 20:37
-
-
Save Anaerin/1fa22d764630f9135e9ed55dee43bddb to your computer and use it in GitHub Desktop.
Merge Sort for Javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
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
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.