Divide and ConquerMerge Sort
Fork
Share
Fullscreen
Sign In
JavaScript
C++
Java
Building
Play
0 / 1
Speed
0
2
4
README.md
bottomUp.js
topDown.js
// import visualization libraries {...}
// define tracer variables {...}
// logger {...}
function mergeSort(start, end) {
if (Math.abs(end - start) <= 1) return;
let mergeFrom = 0;
let mergeTo = 1;
let width;
let i;
for (width = 1; width < end; width *= 2) {
// visualize {...}
for (i = 0; i < end; i += 2 * width) {
merge(mergeFrom, i, Math.min(i + width, end), Math.min(i + 2 * width, end), mergeTo);
}
// this could be copy(mergeTo, mergeFrom, start, end);
// but it is more effecient to swap the input arrays
// if you did copy here, you wouldn't need the copy at the end
mergeFrom = (mergeFrom === 0 ? 1 : 0);
mergeTo = 1 - mergeFrom;
}
if (mergeFrom !== 0) {
// visualize {...}
copy(mergeFrom, mergeTo, start, end);
}
}
function merge(mergeFrom, start, middle, end, mergeTo) {
let i = start;
let j = middle;
let k;
// in an actual merge implementation, mergeFrom and mergeTo would be arrays
// here for the ability to trace what is going on better, the arrays are D[mergeFrom] and D[mergeTo]
// visualize {...}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Contributed by
64json
bbarry
Yee172
Delete File