Learning Journal

2/5/2024

Sort an Array - Merge Sort Bottom Up approach 2nd attempt

function sortArray(nums:number[]):number[] {
    const aux = Array(nums.length);

    for(let size = 1; size < nums.length; size*=2) {

        for(let lo = 0; lo <= nums.length - size; lo+= 2*size) {
            const mid = lo + size - 1, hi = Math.min(lo + 2*size - 1, nums.length - 1);
            merge(nums, aux, lo, mid, hi);
        }
    }
    
    return nums;
}

function merge(a:number[], aux:number[], lo:number, mid:number, hi:number) {

    for(let i = lo; i <= hi; i++) {
        aux[i] = a[i];
    }


    let pLo = lo, pHi = mid + 1;

    for(let i = lo; i <= hi; i++) {
        if(pLo > mid) a[i] = aux[pHi++];
        else if(pHi > hi) a[i] = aux[pLo++];
        else if(aux[pLo] < aux[pHi]) a[i] = aux[pLo++];
        else  a[i] = aux[pHi++];
    }
}


function sortArray(nums:number[]):number[] {
    const aux = Array(nums.length);

    for(let size = 1; size < nums.length; size*=2) {

        for(let lo = 0; lo <= nums.length - size; lo+= 2*size) {
            const mid = lo + size - 1, hi = Math.min(lo + 2*size - 1, nums.length - 1);
            merge(nums, aux, lo, mid, hi);
        }
    }
    
    return nums;
}

function merge(a:number[], aux:number[], lo:number, mid:number, hi:number) {

    for(let i = lo; i <= hi; i++) {
        aux[i] = a[i];
    }


    let pLo = lo, pHi = mid + 1;

    for(let i = lo; i <= hi; i++) {
        if(pLo > mid) a[i] = aux[pHi++];
        else if(pHi > hi) a[i] = aux[pLo++];
        else if(aux[pLo] < aux[pHi]) a[i] = aux[pLo++];
        else  a[i] = aux[pHi++];
    }
}

I just figured why we need to set the condition for ending the inner for loop to be lo <= nums.length - size.

It is because mid = lo + size - 1 and we need there is always at least 1 array to merge. If there is one array to merge, the last clause of the if-else series in the merge function will be executed to copy the element from aux back to the original array.

If we want there is always at least 1 arrary to merge, the mid point can not pass the last element, which is nums.length - 1, so, mid <= nums.length -1, thus lo + size - 1 <= nums.length -1. So, lo <= nums.length - size.