Merge Sort (Simple way to understanding Merge Sort)

#algorithms #dsa #sorting #mergesort

We are provided with an array with items and break down this array until each item is separated with each other and sorted. After that, they are merged to return the combined array of items sorted. That’s what merge sort is going to be doing.
So simple! Let’s get started without further ado.

We start comparing items with each other, if an item is less than another, it goes to the combined array and increment index of the array of that smaller item.

Diagrams below explain well the algorithm used to quickly sort with merge.

function merge(array1, array2) {
    let combined = []
    let i = 0
    let j = 0
    while(i < array1.length && j < array2.length) {
        if(array1[i] < array2[j]) {
            combined.push(array1[i])
            i++
        } else {
            combined.push(array2[j])
            j++
        }
    }
    while(i < array1.length) {
        combined.push(array1[i])
        i++
    }
    while(j < array2.length) {
        combined.push(array2[j])
        j++
    }
    return combined
}

function mergeSort(array) {
    if(array.length === 1) return array

    let mid = Math.floor(array.length/2)
    let left = array.slice(0,mid)
    let right = array.slice(mid)

    return merge(mergeSort(left), mergeSort(right))
}

Test Merge sort by calling this function: mergeSort([1,3,7,8,2,4,5,6])