Skip to content

Instantly share code, notes, and snippets.

@aquaductape
Last active June 20, 2019 16:28
Show Gist options
  • Save aquaductape/c91cdd49f448962972dfe0725b17535e to your computer and use it in GitHub Desktop.
Save aquaductape/c91cdd49f448962972dfe0725b17535e to your computer and use it in GitHub Desktop.
most merge sort solutions are top down, which copy the array. I need an approach to mutates the array which is merge bottom up
const mergeSortBottomUp = arr => {
const length = arr.length;
let step = 1;
while (step < length) {
let left = 0;
while (left + step < length) {
mergeBottomUp(arr, left, step);
left += step * 2;
}
step *= 2;
}
return arr;
};
const mergeBottomUp = (arr, left, step) => {
const right = left + step;
const end = Math.min(left + step * 2 - 1, arr.length - 1);
const temp = [];
let leftMoving = left;
let rightMoving = right;
for (let i = left; i <= end; i++) {
if (
// similar but more powerfull/efficient compared to
// checking if arr[rightMoving](right pointer) is out of bounds or after end point.
// Avoids problem if value is actually undefined
// |
// |
// V
(arr[leftMoving] <= arr[rightMoving] || rightMoving > end) &&
leftMoving < right
// ^^^ sometimes leftMoving will into the right half territory, this will cause duplication.
) {
temp[i] = arr[leftMoving];
leftMoving++;
} else {
temp[i] = arr[rightMoving];
rightMoving++;
}
}
for (let i = left; i <= end; i++) {
arr[i] = temp[i];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment