After spending some time working on a merge sort implementation in TypeScript, I noticed that half of my array seems to be missing from the final result. Can someone with more experience shed some light on why this might be happening?
Source:
function mergeSort(arr:number[]):number[]{
if(arr.length <= 1){
return arr;
}
const half:number = Math.floor(arr.length/2);
const first:number[] = mergeSort(arr.slice(0,half));
const second:number[] = mergeSort(arr.slice(half + 1));
return merge(first, second);
}
function merge(a:number[], b:number[]):number[]{
const c:number[] = [];
while(a.length && b.length){
if(a[0]<b[0]){
c.push(a.shift()!);
}else{
c.push(b.shift()!);
}
}
while(a.length){
c.push(a.shift()!);
}
while(b.length){
c.push(b.shift()!);
}
return c;
}
console.log(mergeSort([4, 53, 22, 10, 2, 74, 91, 33, 25, 14, 19, 100, 256, 81, 7, 300]));
Current output: [4, 10, 14, 33, 74, 81, 100, 300] Expected output: [2, 4, 7, 10, 14, 19, 22, 25, 33, 53, 74, 81, 91, 100, 256, 300]
Your insights will be greatly appreciated!