Merge Sort
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
const input = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function mergeSort(array) {
if (array.length === 1) {
return array;
}
// Split Array into right and left
const middle = Math.round(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
console.log({ left, right });
return merge(mergeSort(left), mergeSort(right));
}
function merge(a = [], b = []) {
const result = [];
let r1 = 0;
let r2 = 0;
let i = 0;
while (r1 < a.length && r2 < b.length) {
if (a[r1] < b[r2]) {
result[i] = a[r1];
r1++;
} else {
result[i] = b[r2];
r2++;
}
i++;
}
while (r1 < a.length) {
result[i] = a[r1];
r1++;
i++;
}
while (r2 < b.length) {
result[i] = b[r2];
r2++;
i++;
}
console.log({ result });
// result.concat(a.slice(r1)).concat(b.slice(r2)); //ignore last two while loops
return result;
}
console.log(mergeSort(input));
JavaScript
INFO