Skip to content

Instantly share code, notes, and snippets.

@DonkeyKongJr

DonkeyKongJr/MergeSort.js

Last active May 28, 2020
Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

@DonkeyKongJr DonkeyKongJr commented May 28, 2020

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
You can’t perform that action at this time.