Learning Journal

1/30/2024

Merge Sort with Bottom Up approach #2nd attempt

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

    for(let sz = 1; sz < nums.length; sz += sz) {
        // merge each pair of sub-arrays of size sz
        for(let i = 0; i < nums.length - sz; i += 2*sz) {
            merge(nums, aux, i, i +sz -1, Math.min(i + 2*sz - 1, nums.length - 1));
        }        
    }

    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 sz = 1; sz < nums.length; sz += sz) {
        // merge each pair of sub-arrays of size sz
        for(let i = 0; i < nums.length - sz; i += 2*sz) {
            merge(nums, aux, i, i +sz -1, Math.min(i + 2*sz - 1, nums.length - 1));
        }        
    }

    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++];
    }

}

This is my second attempt at solving the problem Sort an Array using a bottom-up approach. Let me try to explain what it does again.

Basically, the algorithm merges each pair of the sub-arrays into a bigger sorted array, going from the size of 1 until it almost reaches the size of the original array, double the size after each iteration. During the last iteration, it merges an array with the size of 2 to the power of something almost equal to the size of the original array to the rest of the array (which is already sorted).

During each iteration, the algorithm goes over the original array, from index 0 to the last one, considers each pair of size sz, and merges them in a sorted order.