Understanding Mergesort: Sorting Made Simple | Recursion Series

foreign hey everyone this is William welcome back for another episode today we are continuing to talk about divide and conquer algorithms and in fact we're going to be talking about arguably one of the most influential Divine conquer algorithms out there the merge sort algorithm so let's get into it what is merge sort is a very efficient sorting algorithm that runs in a worst case time complexity of Big O of n log n this makes it a popular choice for sorting large data sets as its performance is relatively unaffected by the input size it works as a divide and conqueror sorting algorithm by breaking down a list of items into smaller sub lists and then merging them back together in a sorted manner merge sort operates in two phases a divide phase followed by a conquer phase during the Divide phase the list of items is repeatedly divided into smaller sub lists until each sublist consists of only one item in the conquer phase the sub lists are combined back together in a sorted manner by comparing the first elements of the sublists and merging them back together in order this process is repeated until all the sub lists have been merged back into a single sorted list the space complexity of merge sort is Big O of n this means that the amount of memory required by the algorithm grows linearly with the size of the input data in merge store the main source of memory usage is the storage required to hold the sublists being merged together during each iteration of the algorithm two sub lists are merged together into a single larger sub list the size of these sublist doubles with each iteration so the maximum amount of memory required is proportional to the size of the input let's have a look at a simple example of the merge sort algorithm in action suppose we have the following list of numbers and we want to sort them what merch sort will do is repeatedly split

the list into until the list can be split no further this is the Divide phase let's have a look foreign and then we go into the conquer phase this is where we merge together the lists on the way back up in the beginning the lists consist of just individual elements that are being merged back together into lists containing two sorted values foreign is that the two lists that we merged together on the way up are themselves already sorted this is key because it is what allows us to merge the list together efficiently in the end we end up with two sorted lists containing four values each which we can merge together into a final fully sorted list foreign

we just had a look at the animated version of the merge sort algorithm now let's have a look in more detail at what happens during each of the two phases of the algorithm let's suppose again that we have a new list this time containing six elements that we want to sort during the Divide phase we want to split each of the existing segments in half until each segment consists of only one element the way we keep track of each segment is by the pair of indices representing the range of that segment this allows us to determine which portion of the list we are currently working with I usually refer to these indices as low and high low for the lower index and high for the upper index to perform a segment split we need to locate the midpoint of the segment we can do this by taking the average of low and high that is low plus High divided by two and with that information we can determine the new bounds of the left and the right segments in the example on the screen the low endpoint of the segment is zero and the high end point is 5 so the midpoint is 2 after integer Division and once we know the midpoint we can split the segment in two the left one being from low to the midpoint and the right one from the midpoint plus one to high we can apply this process again to split the next set of segments in half and after a couple rounds of division all the segments have a length of one and this marks the end of The Divide

phase and the beginning of the conquer phase where we sort the segments on the way up for the conquer phase just focus on the lowest segments first what we want to do is sort the left and the right segments into a new list as we recurse upwards so in the left Branch we would sort seven before nine and in the right Branch we would sort 2 before 6. after sorting the bottom layer we move up and merge the segments seven and nine with five and two and six with four and repeat the same process for the final segments and in the end we get a fully sorted list

list awesome now that we understand how merge sort Works let's have a look at some pseudocode which more or less resembles python on the first line we declare the merge sort function which takes the list we want to sort as input upon entering the function we verified that the length of the list is zero and if it is then return an empty list the primary reason for checking if the length of the list is greater than zero before calling the merge sort algorithm is to prevent the occurrence of a negative index when the length of the list is zero following that we can invoke the internal merge sort function by passing the initial lower and upper bounds since the indices are inclusive we provide 0 and the length of the list minus one as initial values now let's have a look at what's going on inside the recursive merge sort function the base case for the merge sort is that the interval size is a single element which happens when the lower index is equal to the upper index in this case we can return a new list containing the sole value at the current index position it's important to note here that we want to return a deep copy of the list rather than a shallow copy this ensures that we're working with a new copy of the list instead of just a reference and this is crucial because a shallow copy would result a bug in the Sorting process next find the middle index of the segment by adding low plus High divided by 2 then use the middle index to recursively compute the new left and right segments notice that the left segment spans between low to mid and the right segment spans between mid plus 1 to high so there is no overlap between each the final step is to merge the left and the right segments on the recursive callback and this is where the conquer phase kicks in

let's take a closer look at what happens inside the merge function the input to the function is two sorted lists left and right and the output is a single larger sorted list that combines the left and the right lists together since are already sorted we take advantage of this fact to efficiently construct a new sorted list during their merging process to keep track of two new variables L and R which are the indices for what position we're at in the left and the right lists respectively this wild condition says while either the left index or the right index hasn't made it to the end of the list continue iterating this ensures that we merge the entirety of each list into the new sorted list before exiting the loop the following code adds the smallest remaining element from either the left or the right list to the new sorted list we also need to handle the scenario where we reached the end of one of the lists and need to add the remaining elements from the other list to the sorted list let's look at a quick example suppose I have the already sorted lists left and right and we want to merge them into a larger sorted list initially I have the indices lnr beginning at the start of each list then we compare the value in the left list with right list and add the smaller one to the sorted list since we added an element from the left let's increment the left index then repeat the same thing compare the elements in the left and the right list and add the smaller one to the larger sorted list I'll let the animation play for the next couple slides foreign the list together return the sorted list from the merge function and that's basically how merge sort Works in a nutshell and guys that's all I have for now thank you for sticking around till the end please like this video If you learned something about merge sort And subscribe for more content and I'll see you in the next one