Skip to content

Instantly share code, notes, and snippets.

@JakobJingleheimer
Created August 3, 2018 08:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JakobJingleheimer/fe94294cf586cb0651c6ab99a555d901 to your computer and use it in GitHub Desktop.
Save JakobJingleheimer/fe94294cf586cb0651c6ab99a555d901 to your computer and use it in GitHub Desktop.
recursive merge sort: Average runtime O(log n)
function mergeSort(arr, low = 0, top = arr.length - 1) {
if (low < top) {
const mid = Math.floor((low + top) / 2);
mergeSort(arr, low, mid);
mergeSort(arr, mid+1, top);
merge(arr, low, mid, top);
}
return arr;
}
function merge(arr, low, mid, top) {
const lowHalf = new Array(mid - low);
const topHalf = new Array(top - mid);
// load elements from arr into each "half" array
for (let k = mid; k > -1; k--) lowHalf[k] = arr[k];
for (let k = top; k > mid; k--) topHalf[k-mid-1] = arr[k];
let a = top;
let l = lowHalf.length - 1;
let t = topHalf.length - 1;
while (~a) {
const elmLow = lowHalf[l];
const elmTop = topHalf[t];
if (!~t || elmLow > elmTop) {
arr[a--] = elmLow;
--l;
} else {
arr[a--] = elmTop;
--t;
}
}
return arr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment