Learning Journal

1/28/2024

Merge Sort

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

    sort(nums, aux, 0, nums.length - 1);

    return nums;

};


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

    const mid = lo + Math.floor((hi - lo)/2);

    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);

}

function merge(a:number[], aux:number[], lo:number, mid:number, hi:number) {
    // Copy the part of a that needs to be merged to aux
    for(let i = lo; i <= hi; i++) {
        aux[i] = a[i];
    }

    let iLo = lo, iHi = mid + 1;

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

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

    sort(nums, aux, 0, nums.length - 1);

    return nums;

};


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

    const mid = lo + Math.floor((hi - lo)/2);

    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);

}

function merge(a:number[], aux:number[], lo:number, mid:number, hi:number) {
    // Copy the part of a that needs to be merged to aux
    for(let i = lo; i <= hi; i++) {
        aux[i] = a[i];
    }

    let iLo = lo, iHi = mid + 1;

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

}

This is my attempt to solve the Sort an Array problem using merge sort.

Merge sort algorithm involves 2 functions: merge and sort.

The merge function is to merge 2 already sorted arrays into 1 sorted array. The sort function is to divide an array into 2 almost equal sub-arrays, recursively sort each array, and then merge two sub-arrays back using the merge function.

The terminate condition of the function sort is when the lower bound is greater or equal to the higher bound, which is when the length of the sub-array is 0. When sort function reaches the terminate condition, it will go back one step, now the sub-array has 1 element. What it does is just put that element back into the original array. Even though the function merge named "merge", it is the one that does the sorting.