Learning Journal

1/29/2024

Merge Sort #2nd attempt

function sortArray(nums: number[]):number[] {
    const aux = Array(nums.length);
    
    sort(nums, aux, 0, nums.length - 1);

    return nums;
}

function sort(a:number[], aux:number[], lo:number, hi:number):void {
    if(lo >= hi) return;

    // Divide a into 2 half
    const mid = lo + Math.floor((hi - lo)/2);

    // Sort the first half
    sort(a, aux, lo, mid);
    // Sort the second half
    sort(a, aux, mid + 1, hi);

    // Merge them together
    merge(a, aux,  lo, mid, hi);
}

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);
    
    sort(nums, aux, 0, nums.length - 1);

    return nums;
}

function sort(a:number[], aux:number[], lo:number, hi:number):void {
    if(lo >= hi) return;

    // Divide a into 2 half
    const mid = lo + Math.floor((hi - lo)/2);

    // Sort the first half
    sort(a, aux, lo, mid);
    // Sort the second half
    sort(a, aux, mid + 1, hi);

    // Merge them together
    merge(a, aux,  lo, mid, hi);
}

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 solving Sort an Array problem using merge sort. Some lessons I learned from this attempt:

Always remember to add a base case in a recursive function.
The sorting actually happens in the second for loop of the merge function. In this for loop, each element is put back to array a in order. Even though the pre-condition of the merge is that the two sub-arrays are already sorted, when we reach the base case, two sub-arrays only contain 1 element each, which means we actually sort by comparing these two elements and then putting them back into the original array.
The second for loop in the merge function goes over all places of the portion that needs to be merged in the original array and considers which element among the two elements in aux and pointed by the two pointers that need to be in each place.