Last active
April 30, 2020 12:41
-
-
Save deemaxx/8bd8ac8c0da9c9214929a6b0018525d5 to your computer and use it in GitHub Desktop.
Merge and sort 1 or more arrays
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const array = [0, 1, 3, 4, 31, 2, 4, 6, 7, 10, 23, 30]; | |
/** | |
* Merge Sort is a divide and conquer algorithm. It divides input array in two halves, | |
* calls itself for the two halves and then merges the two sorted halves. | |
* time complexity: O(nLogn) | |
* space complexity: O(n) | |
* @param arr | Array<number> | |
* @return Array<number> | |
*/ | |
function mergeSort(arr) { | |
if (!Array.isArray(arr)) { | |
throw new Error('input must be an array'); | |
} | |
if (arr.length > 1) { | |
let mid = arr.length / 2; | |
let leftArr = arr.slice(0, mid); | |
let rightArr = arr.slice(mid); | |
mergeSort(leftArr); | |
mergeSort(rightArr); | |
let i = j = k = 0; | |
while (i < leftArr.length && j < rightArr.length) { | |
if (leftArr[i] < rightArr[j]) { | |
arr[k] = leftArr[i]; | |
i++; | |
} | |
else { | |
arr[k] = rightArr[j]; | |
j++; | |
} | |
k++; | |
} | |
while (i < leftArr.length) { | |
arr[k] = leftArr[i]; | |
i++; | |
k++; | |
} | |
while (j < rightArr.length) { | |
arr[k] = rightArr[j]; | |
j++; | |
k++; | |
} | |
return arr; | |
} | |
} | |
mergeSort(array); // result: [ 0, 1, 2, 3, 4, 4, 6, 7, 10, 23, 30, 31 ] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment