Skip to content

Instantly share code, notes, and snippets.

@tqmvt
Created September 27, 2022 15:24
Show Gist options
  • Save tqmvt/6d5b306e58e5bf8bfad23030b6ab7862 to your computer and use it in GitHub Desktop.
Save tqmvt/6d5b306e58e5bf8bfad23030b6ab7862 to your computer and use it in GitHub Desktop.
Merge Sort Algorithm
// merge the two arrays: left and right
function merge(left, right) {
let resultArray = [],
leftIndex = 0,
rightIndex = 0;
// concatenate values into the resultArray in order
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]);
leftIndex++; // move left array cursor
} else {
resultArray.push(right[rightIndex]);
rightIndex++; // move right array cursor
}
}
// concat here because there will be one element remaining
// from either left OR the right
return resultArray
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
// Merge Sort Implentation (Recursion)
function mergeSort(unsortedArray) {
// No need to sort the array if the array only has one element or empty
if (unsortedArray.length <= 1) {
return unsortedArray;
}
// In order to divide the array in half, we need to figure out the middle
const middle = Math.floor(unsortedArray.length / 2);
// This is where we will be dividing the array into left and right
const left = unsortedArray.slice(0, middle);
const right = unsortedArray.slice(middle);
// Using recursion to combine the left and right
return merge(mergeSort(left), mergeSort(right));
}
console.log(mergeSort([3, 43, 23, 4, 32, 65, 43, 45, 34, 5, 23]));
// Complexity of Mergesort is O(nlogn)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment