Merge Sort
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
let array = [6, 5, 3, 1, 8, 7, 2, 4];
// let array = [99,44,6,2,1,5,63,87,283,4,0];
function mergeSort(arr) {
// debugger;
let len = arr.length;
if (len <= 1) {
return; //base case
}
let left = [];
let right = [];
let left_size = Math.floor(len / 2);
let right_size = len - left_size;
for (let i=0; i<left_size;i++) {
left.push(arr[i]);
}
for (let i=left_size; i<len;i++) {
right.push(arr[i]);
}
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
function merge(arr, left, right) {
let l = 0;
let r = 0;
let i = 0;
while (l < left.length && r < right.length && i < arr.length) {
if (left[l] < right[r]) {
arr[i] = left[l];
l++;
} else {
arr[i] = right[r];
r++;
}
i++;
}
while (l < left.length) {
arr[i] = left[l];
l++;
i++;
}
while (r < right.length) {
arr[i] = right[r];
r++;
i++;
}
}
mergeSort(array);
console.log(array);
JavaScript
INFO