DEV Community

loading...

Sorting Algorithms: Merge Sort

keeks5456
Full-stack Software Engineer
・3 min read

On today's series of Sorting Algorithms, I will be getting down with the Merge Sort Algorithm!

What Is A Merge Sort Algorithm?

Merge Sort is described as a divide and conquer algorithm. What this means is, we start off with an array of items, we must divide that array in half. Now that we have two arrays, we start comparing each element to the opposing array. Whichever is smallest, must go into the empty array. As a result, we return a new sorted array.


Now, before we get into the code, like the algorithm itself, we must break down how to implement merge sort in two functions!


Merge a Nearly Sorted array

In this function, we will be taking our array, splitting it down the middle, giving us two arrays. With recursion, we will keep splitting those two arrays until they are an array containing one element

The PseudoCode

  • Break up the array into halves until you have arrays that are empty or have be an element.
  • Once you have small & sorted arrays, merge those arrays with each other until they are back at full length.

The Code

//helper method to sort the array
const mergeSort = (arr) =>{
  //base case if our array length is too small.
  if(arr.lenght <= 1) return arr 

  //first split the array in half
  let mid = Math.floor(arr.length / 2)
  //assign the left half of the array from beginning to middle
  let left = mergeSort(arr.slice(0, mid))
  //assign the right half of the array from mid to end of array
  let right = mergeSort(arr.slice(mid))
  //return sorted array by calling merge function to merge the now sorted pieces together
  return mergeSort(left, right)
}
Enter fullscreen mode Exit fullscreen mode

Merging Arrays

How we can approach this function is, with our two split up arrays from our mergeSort function, we will now start comparing if an element is the smallest in the left or right array, that element will get pushed into our results array.

The Pseudocode

  • Create an empty array, look at the smallest values in each array
  • while there are still values we haven't looked at,
  • if the value in the first array is smaller than the second array, push that value into the results and move to the next element in the first array.
  • This same logic goes for the second array, if the value there is smallest, push that to the results array.
  • Once we exhaust one array, push the remains from the other to the results array and return.

The Code


//create the merge function, it takes in two arrays 
const merge = (arr1, arr2) =>{
  //create a reults array to return merge srted array
  let results = []
  //assign i and j to 0 as comparison pointers 
  let i = 0, j = 0
  //create a while loop going through both arr1 & arr2 loping at each index
  // while there are still elements in our arrays, do this
  while(i < arr1.length && j < arr2.length){
    //ask if arr1[i] is less that arr2[j]
    if(arr1[i] < arr2[j]){
      //if arr1[i] is smaller, push that number in our results array
      results.push(arr1[i])
      //move to the next value in arr1
      i++
    } else {
      //if arr2[j] is smallest instead push that to our array
      results.push(arr2[j])
    }
  }
  //since there is a possibility of remaining elements in either of the arrays we must lop through them again while they are not empty
  //while there are still elements in arr1, iterate through them and push them to results array, these remaining elements will already be sorted because of merge helper function
  while(i < arr1.length){
    results.push(arr1[i])
    i++
  }
   //while there are still elements in arr2, iterate through them and push them to results array, these remaining elements will already be sorted becasue of merge helper funtion
  while(j < arr2.length){
    results.push(arr2)
    j++
  }
  return results
}
Enter fullscreen mode Exit fullscreen mode

Without Comments

function mergeSort(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++
    }
  }

  return results
}


function merge(arr){
  if(arr.length <= 1) return arr

  let middle = Math.floor(arr.lenght / 2)
  let left = mergeSort(arr.slice(0, middle))
  let right = mergeSort(arr.slice(middle))
  return merge(left, right)
}
Enter fullscreen mode Exit fullscreen mode

Time and Space Complexity

  • The time complexity of a merge sort algorithm at best, average, and worst case is O(n log n).
  • The space complexity of this algorithm is O(n). ***

The Conclusion

The Merge Sort Algorithm is highly more effective than implementing Bubble Sort or Selection Sort. It simply breaks down the array only to build it back up again. Now that w are diving into the more advanced sorting algorithms, I will be talking about Quicksort and the advantages it has in sorting!

Until Next time!
Happy Coding :)

Discussion (0)