DEV Community

loading...
Cover image for Merge Sort Algorithm

Merge Sort Algorithm

Damon Marc Rocha II
Hi, my name is Damon Rocha. I am a flatiron software engineering graduate. I have been coding for 4 years now.
・2 min read

The merge sort algorithm is an effective algorithm to use when sorting a list. To sort a list, using the merge sort, two steps must be taken; split the list until the sublists are compromised of only one element and merge the sublists until the sorted array is reached.

Implementation

So first we must have a function which can split the array until its length is equal to one

let unsorted_array = [3,5,7,2,1]

let merge_sort = (arr) => {
    let mid = arr.length/2
    let first_half = arr.slice(0, midp
    let second_half = arr.slice(mid, array.length)
    if (arr.length < 2){
       return arr
    }
    else{
       return merge(merge_sort(first_half), merge_sort(second_half))
    }
}
Enter fullscreen mode Exit fullscreen mode

The code above is pretty straight forward; an unsorted array and merge_sort function are created. This function splits the array and passes the two halves into itself until the array is less than two in length. Once this is achieved the single subarray are all run through the merge function.
The next part we need to implement is the merge function. This function will return a sorted array composed of the two halves.

let merge = (first_half, second_half) => {
    let sorted = []
    while(first_half.length !== 0 && second_half.length !== 0){
          let currentMin = find_min_and_remove(first_half, second_half)
          sorted.pus(currentMin)
    return sorted.concat(first_half).concat(second_half)
Enter fullscreen mode Exit fullscreen mode

The merge function appends the minimum from the two lists to the sorted array and also removes this item from its corresponding list. When one of the lists is empty the remaining elements are appended to sorted. The double append here is due to the fact that either list could become empty and allows for the absence of a check to determine which list is empty.
Lastly, we must create the find_min_and_remove function. This function will compare the first items of every list to find the minimum

let find_min_and_remove = (first, second) => {
    let min_first = first[0]
    let min_second = second[0]
    if (min_first < min_second)
       return first.shift()
    else:
       return first.shift()
Enter fullscreen mode Exit fullscreen mode

Since the list will be split into single items the first element of every list will be the minimum. So the list that contains the smaller element will have it removed and sent back to be appended to the sorted list in the merge function.
And that is it.

Discussion (0)