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)
}
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
}
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)
}
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 :)
Top comments (0)