Skip to content

Instantly share code, notes, and snippets.

@scalactic
Created July 9, 2021 17:30
Show Gist options
  • Save scalactic/038d6a6a77cd61b53891f3e2cc244512 to your computer and use it in GitHub Desktop.
Save scalactic/038d6a6a77cd61b53891f3e2cc244512 to your computer and use it in GitHub Desktop.
merge sort in javascript
function merge(arr, l, m, r) {
let i, j, k;
let n1 = m - l + 1;
let n2 = r - m;
/* create temp arrays */
let L = new Array(n1);
let R = new Array(n2);
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the sub-array of arr to be sorted */
function mergeSort(arr, l, r) {
console.log(arr);
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and h
let m = Math.floor(l + (r - l) / 2);
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
const unsorted = [8, 7, 6, 5, 4, 3, 2, 1, -4, -1000, 327, 14011904, 115011017];
console.log(unsorted.length);
mergeSort(unsorted, 0, unsorted.length - 1);
console.log(unsorted);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment