Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
30 Days of Algorithms - Day 06 Merge Sort
/**
* Recursively split, sort, and re-merge the array.
* @param unsortedArray
* @returns {*[]|*}
*
* Big-O:
*
* Space complexity : O(n)
* Time complexity : O(n Log n)
*/
const mergeSort = (unsortedArray) => {
/*
* If there is only one item, it's already sorted :-)
*/
if (unsortedArray.length <= 1) return unsortedArray;
/*
* Determine the mid-point of the dataset to divide & conquer.
*/
const middle = Math.floor(unsortedArray.length / 2);
/*
* Split the array into left & right halves.
*/
const left = unsortedArray.slice(0, middle);
const right = unsortedArray.slice(middle);
/*
* Recursively merge the halves.
*/
return merge(
mergeSort(left), mergeSort(right)
);
}
/**
* Merge the two arrays: left and right
* @param {array} left
* @param {array} right
* @returns {*[]}
*/
const merge = (left, right) => {
let sorted = [],
li = 0,
ri = 0;
/*
* We will concatenate values into the resultArray in order
*/
while (li < left.length && ri < right.length) {
if (left[li] < right[ri]) {
sorted.push(left[li]);
li++;
}
else {
sorted.push(right[ri]);
ri++;
}
}
/*
* We need to concat here because there will be one element remaining
* from either left OR the right
*/
return sorted
.concat(left.slice(li))
.concat(right.slice(ri));
}
var numbers = [
62, 52, 88, 51, 26, 40, 13, 44,
83, 30, 10, 31, 99, 79, 81, 45,
33, 97, 17, 96, 38, 50, 39, 22,
47, 61, 20, 85, 75, 16, 15, 95,
11, 71, 21, 86, 24, 28, 46, 5,
89, 54, 70, 87, 35, 42, 69, 82,
84, 76, 60, 98, 77, 68, 8, 66,
96, 78, 90
];
console.log(
mergeSort( numbers )
);
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.