Merge Sort

There is a family of sorting algorithms that can improve time complexity from O(n^2) to O(n log n)

It was created by Jonathan Van Norman in 1948.

 

it is a combination of two things - merging and sorting.

it works by decomposing an array into smaller arrays,

spliting up the larger array we are trying to sort into smaller sub arrays all the way down.

 

first, splitting up until we end up with sorted arrays which are 0 or 1 element.

and merging sorted arrys until we finish.

we just need to merge two sorted arrays, emerging function.

 

this function should run in O(n+m) time and O(n+m) space.

iterate over n and m

---

Mergin Arrays Pseudocode

• Create an empty array, take a look at the smallest values in each input array.
• While there are still values we haven't looked at.
• if the first item is smaller we put that in our result array and then we move on to the next item in the first row.
• If the first array is larger the item in the first array than the value in our second array.
• once we finish one array we just push all the remaining values from the other array in.

 

// Merges two already sorted arrays
function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;
}
merge([100,200], [1,2,3,5,6])

 

---

mergeSort Pseudocode

most merge sort implementation to use resursion.

• keep breaking up into halves.(useing slice)
• once we have those small arrays we merge them back using our merge function above.
• once the array has been merged back together we return the merged array at the end.

// Recrusive Merge Sort
function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, sright);
}

mergeSort([10,24,76,73])

 

 

Big-O Complexity Chart

www.bigocheatsheet.com/