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