Sample 1:
function mergesort(arr){
if (arr.length > 1){
let mid = parseInt(arr.length/2);
let left = arr.slice(0,mid);
let right = arr.slice(mid);
mergesort(left);
mergesort(right);
return merge(left,right);
}
else return arr;
}
Sample 2:
function mergesort(arr){
if (arr.length > 1){
let mid = parseInt(arr.length/2);
let left = mergesort(arr.slice(0,mid));
let right = mergesort(arr.slice(mid));
return merge(left,right);
}
else return arr;
}
Merge function:
function merge(left, right){
let leftIdx = 0, rightIdx = 0;
const result = [];
while (leftIdx < left.length && rightIdx < right.length){
if (left[leftIdx] < right[rightIdx]){
result.push(left[leftIdx++])
}
else{
result.push(right[rightIdx++])
}
}
let res = [...result, ...left.slice(leftIdx), ...right.slice(rightIdx)];
return res;
Sample 2 is giving the correct output but sample 1. Can you explain the difference between both samples.
let arr = [5, 3, 7, 2, 9, 12, 4];
Applying sample 1 on arr gives [2, 5, 3, 7, 9, 12, 4] as output that is obviously incorrect.