Merge sort with TypeScript-CodePudding

I have tried to implement a simple merge sort in TypeScript. Unfortunately half of my array is missing from the result. Could someone more experienced explain to me please why it is missing?

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]

Thank you for your time and answer!

CodePudding user response：

I think you are loosing a number at half index each time you split your array.

Because neither of these two slices include item at half index.

const first:number[] = mergeSort(arr.slice(0,half));
const second:number[] = mergeSort(arr.slice(half   1));

To fix that you need to include that item either in the first half:

const first:number[] = mergeSort(arr.slice(0,half   1));

Or include it in to the second half:

const second:number[] = mergeSort(arr.slice(half));