Skip to content

Instantly share code, notes, and snippets.

@DonkeyKongJr
Last active May 28, 2020 13:48
Show Gist options
  • Save DonkeyKongJr/d03a7a491e60ad779f41b2aa2a76bb7a to your computer and use it in GitHub Desktop.
Save DonkeyKongJr/d03a7a491e60ad779f41b2aa2a76bb7a to your computer and use it in GitHub Desktop.
Merge Sort in JavaScript
const mergeSort = (unsortedArray) => {
// Check if the length is lower or equal to 1, otherwise return input.
// This is also our break condition for the recursion
if (unsortedArray.length <= 1) {
return unsortedArray;
}
// Split input array in two equally parts when possible.
// The half of the length could possibly be an floating number 3 / 2 = 1.5,
// so we use Math.floor to get an whole number by remove the decimal part.
const middleIndex = Math.floor(unsortedArray.length / 2);
const leftArray = unsortedArray.slice(0, middleIndex);
const rightArray = unsortedArray.slice(middleIndex);
// Use recursion on the left and right part to break it down
return mergeParts(mergeSort(leftArray), mergeSort(rightArray));
};
const mergeParts = (leftArray, rightArray) => {
let mergedArray = [];
let leftIndex = 0;
let rightIndex = 0;
// Compare left and right items as long as there is a counterpart (index is not out of range).
while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
if (leftArray[leftIndex] < rightArray[rightIndex]) {
mergedArray.push(leftArray[leftIndex]);
leftIndex++;
} else {
mergedArray.push(rightArray[rightIndex]);
rightIndex++;
}
}
// Because there could be some items left on the left or right side we concat all remaining elements.
// In theory there should only be one side affected.
return mergedArray
.concat(leftArray.slice(leftIndex))
.concat(rightArray.slice(rightIndex));
};
@DonkeyKongJr
Copy link
Author

You can find more details in this blog post

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