Skip to content

Instantly share code, notes, and snippets.

@deemaxx
Last active April 30, 2020 12:41
Show Gist options
  • Save deemaxx/8bd8ac8c0da9c9214929a6b0018525d5 to your computer and use it in GitHub Desktop.
Save deemaxx/8bd8ac8c0da9c9214929a6b0018525d5 to your computer and use it in GitHub Desktop.
Merge and sort 1 or more arrays
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