In my last blog I went over recursion. In this blog I’m going to use recursion to write out a sorting algorithm commonly known as merge sort. Merge Sort uses a common algorithm technique called ‘divide and conquer’ to split down the arrays into more easily sortable smaller arrays. Instead of comparing all the elements with each other, merge sort breaks the array down into many smaller arrays and pieces them back together. Imagine merging together two sorted arrays. [1,3,5] and [2,4,6]. You could simply compare the first element of each array to see which one is smaller.
[1,3,5] [2,4,6]
compare 1 and 2
result = [1]
[3,5] [2,4,6]
compare 3 and 2
result = [1,2]
[3,5] [4,6] continue until finished....
[1,2,3,4,5,6]Here we are comparing the first element of each array and always taking the smaller of the two elements. It’s much easier and quicker to merge two sorted arrays than it is to sort an array by comparison. Our first task is to split the array into a bunch of single element arrays.
[5,2,7,3,1,8] [5,2,7] [3,1,8]
[5,2] [7] [3,1] [8]
[5] [2] [3] [1]
From there we will work are way back up by merging the arrays back together.
[2,5] [7] [1,3] [8]
[2,5,7] [1,3,8]
[1,2,3,5,7,8]Now that we have an idea of what we need to do we can write out our code to merge two arrays.
function merge(arr1, arr2){ let result = [] //placeholder array let p1 = 0 //pointer for index of arr1
let p2 = 0 //pointer for index of arr2 while(p1 < arr1.length && p2 < arr2.length){ //while the pointers are still within the bounds of the array
//push the smaller value into our results array if(arr1[p1] < arr2[p2]){
result.push(arr1[p1])
p1++
}
else{
result.push(arr2[p2])
p2++
}
} if(!arr[p1] && arr2[p2]) result = [...result, ...arr2.slice(p2)]
if(arr[p1] && !arr2[p2]) result = [...result, ...arr1.slice(p1)] //if there are leftovers in one of the two arrays add to the end
//of our results array, then return results array return result
}
Now that we have our merge function, we can use it to merge the arrays we break down with our sort function.
function mergeSort(arr){ if(arr.length === 1) return arr //our recursion baseline
let mid = Math.floor(arr.length / 2) //midpoint of our array let left = mergeSort(arr.slice(0, mid)) //recursive call on left
//half of array let right = mergeSort(arr.slice(mid)) //recursive call on right
//half of array return merge(left, right) //return the sorted merged array}
Like we went through last blog, a recursive function recursively calls itself until it hits the baseline, in this case when the array only has one element in it. When it does hit that baseline, the call stack will start to clear with the resolved variables.
mergeSort([3,1,2])
left = mergeSort([3,1])
left = mergeSort([3])
return([3])
right = mergeSort([1]}
return([1])
right = mergeSort([2])
return([2])
the values at the top of the call stack have been resolved and the call stack can begin to clearleft = merge([3], [1])
right = [2]left = [1,3]
right = [2]merge([1,3], [2])return [1,2,3]
I hope that this blog has built on top of your understanding of recursive functions and shed some light on how useful they can be.
