Last active
June 20, 2019 16:28
-
-
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
This file contains hidden or 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 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