Merge Sort Algorithm in Java - Full Tutorial with Source

in this video we are going to code the merge sort sorting algorithm in java in my bubble sort video i got a comment that said can you do merge sort next ask and you shall receive now we know this sorting algorithm is going to be faster it has a complexity of big o of n log n but how much faster does it actually work out to with a real implementation with bubble sort we got up to sorting a million numbers but it still took about 37 minutes with merge sort of course we're going to see how much faster we can do a million integers but we're even going to take it a step further and go to 10 million 100 million even a billion if we can get there if this is your first time watching this channel my name is john and i do a new java tutorial video like this one every single week so be sure to leave a like and hit the subscribe button so you don't miss the new video every week and as always you can get the full source code of this program in the link down in the description so go and get it as with all the sorting algorithm videos so far i start with a little bit of a program set up first i create this array of ins called numbers here we're just starting with a length of 10 so we'll have 10 numbers to sort and then we loop through that array to fill it with random ins essentially between zero and a million so that gives us our unsorted array that we want to sort and then after that we print out the before state the unordered array and then we have the call to our merge sort method which is currently empty that is what we will be writing in this video and then after that merge sort method is called we should have a sorted list and so we just print that array again and we should see it in perfectly sorted order i know we want to just dive head first into the code but before we do it's a good idea to get a mental model of how merge sort works this is a diagram just from the merge sort wikipedia page that gives a pretty good picture of how it works you start out with your unordered array you divide that array into two halves and merge sort each half recursively and then once each half of your array is sorted so this half is in order and this half is in order then you go through a process of merging both of those halves of your array into one array again and that one array will be in order how that merge process actually works is key and we'll get into that more when we get to the code we start with this completely unordered array then we divide it in half into two arrays and then we tell each array to merge sort itself that's the recursive part of this algorithm so you can see here this first array is being split into two halves and then the same merge sort algorithm will be called for each of these halves well the first part of the algorithm is to again split into two halves and merge sort each half so here you can see each half being divided again into two halves then here in the third level of this example we still recursively merge sort each of these very small arrays and again the first step to doing that is dividing them so eventually that gets us down to where we have a one element array for each number in the array that we started with so this is the whole dividing portion of the divide and conquer of this algorithm we divide divide divide into smaller and smaller problems until we get to where all of our arrays just have one element in them and we know that an array with just one element in it it's already in order it can't be out of order there's only one element in it so once we get to that state we start the conquer portion of our divide and conquer algorithm and that is the merging let's take a look at this example merge here so to start with we know that we are merging two arrays that are already sorted we know that each one is in order with itself so here we have 27 and 38 and 3 and 43 each of those are in order with themselves what we do is we start by comparing the first element of each array which here is 27 and 3 and we say which one is smaller and here 3 is smaller we take the one that is smaller and add it to our merged array so here we add three as the first element in our merged array and then since we added three to our array we move over and look at 43. for our other array since we haven't added 27 yet we're still comparing 27 with that next element of the other array so the next step it would be comparing 27 to 43 which one of those is smaller it's 27. so we go ahead and add 27 to our merged array and then since we added 27 we move over to look at 38 so we're comparing 38 to 43 which one is smaller 38 so we go and add that to our merged array so then when we add 38 we now have no elements left in this array that haven't already been added to the merged array when that happens we'll go through all the elements in our other array that still has values yet to be added and just add them all in order in this case all we would have left is 43 so we would just add 43 to our merged array so after that has happened our result is one merged array that has all the elements of the two arrays we were merging all in perfect order for a while what got me is how do we know that doing the comparisons and the adding in that way how does that result in a perfectly ordered merged array well the key is that both of the arrays that we're merging are already in order if neither of these two arrays were in order merging them with the algorithm we just talked about wouldn't work right we're looping through both of these arrays from their lowest values to their largest adding the lowest value that we find to our merged array and then we slowly progress to higher and higher numbers in each of these arrays and keep adding the next lowest one that we find along the way each of these merge steps that we see operate exactly the same way and then this final merge down at the bottom looks more complicated but it's really not we do the exact same thing so now that we've gone through all that let's get to the code so again all the magic in our code is going to be happening in this merge sort method the first thing we want to do here is to create a variable for the length of this input array because we're going to need the length of this input array many times throughout this algorithm so having a variable for it just makes our life a little easier so we'll call it input length and set it equal to input array dot length so remember we are going to be calling this merge sort method recursively which means yes we're going to be starting it by calling it on one larger array but even as it gets further and further down into these sorts of levels here where there's only one or two elements in each array we're going to be calling that merge sort method recursively on smaller and smaller arrays until we're eventually calling it on arrays with just one element in them and we know that arrays with just one element are of course already sorted so actually the first thing we want to do is check that if the input length is less than 2 which of course means we either have an empty array or an array with just one thing in it then we just return so that accounts for like this part of the algorithm here where we have a bunch of arrays with just one element in them we don't divide that into two arrays and have each side sort itself we only have one element in it so we already know it's sorted so this accounts for that if the array that comes in is less than two elements long which is essentially either a zero or a one element array then we just return there's nothing for us to do it's already sorted but if that's not the case if we have two or more elements in the array that we're looking to sort right now then we continue the next thing to do in our algorithm is to divide our array into two arrays to do that we need to get the midpoint of our array which is just half of the input length so if we came in with an input array that was 10 elements long we want to divide it into two arrays split at that fifth element in the midpoint so to do that we'll create another variable we'll call it um mid index and set it equal to the input length divided by two and then we'll actually create our two arrays for the left and right half we'll create an int array call it left half and set it equal to a new int array that we will create and we need to give it a length and we can just use mid index because we know that'll give it half the length of our original array so again if our input array was 10 elements long this mid index would be 5 and our left half array here would have a length of 5 which is what we want now we have to create our right half equals new int array and we also need a length here and to do that we're actually going to use input length minus mid index you might be thinking hey we can just use mid index here also but that ends up not working right for arrays with odd numbers of elements in them so if this input array came in with 9 elements in it then input length divided by two would actually end up being four so the left half would be four elements long and we need to hold the other five elements in the right half so input length minus mid index works great for that that would be nine minus four which gives us the five elements that we need so now we've created these two arrays left half and right half but they don't have any elements in them yet so we actually have to populate them with all the elements from our original larger input array so first we'll fill up the left half by doing four int i equals 0 i less than so what do we want to use here we're just trying to fill up the left half array so we can only loop until the end of that array so we actually want to use is this mid index and then of course increment i i plus plus so we're looping from zero to the length of our left half so this i is what we'll be using as the index of our array and what we want to do here is copy the elements from our original input array into our left half array so to do that we just set left half at i the i index of our left half array to be equal to the input arrays ith element so after this for loop completes our left half array will contain all the elements from the left half of our input array and now we want to fill up the right half array with all of the elements of the right half of our input array so it'll be similar but not exactly the same we can copy paste here as a start here we actually want to start with i at the mid index and loop until i reaches the original input length of our input array and of course still increment i each time so essentially what we're needing to do is loop through the second half of our original input array and that's what this allows us to do here so we start at that mid index at the midpoint and go until the end this input length and we still want to use input array i here but now using i as the index of this left half that we're assigning to doesn't really work again if we have a mid index of 5 we don't want to be starting by setting the fifth element of our left half we want to start at the zeroth element but we still do want to use i here because we do want to be starting at the midpoint of this original input array what we want to modify here is instead of setting left half i we want to set left half of i minus mid index so again for example if we have a mid index of five this will start with five minus five which will be zero the zeroth index which is what we want and then when it moves on to the next one then i will be six and we'll be setting the element at six minus five which will be one the next element in the array and of course also we want to change this to right half instead of left half we don't want to be overriding the left half again we want to be creating the right half essentially what is happening here is we're filling up the right half array that we created with all the elements from the right half of our original input array okay now after all of that is completed we have our left half and right half arrays that contain the left half and right half of our original input array what does our algorithm say has to happen next well what we do is we merge sort each of those two arrays and then later we'll merge them together so how do we tell our algorithm to merge sort each half of our array well that's actually the simplest part of this so far we have a merge sort method that we're writing so all we have to do is recursively call it with our left and right halves so we will literally just say merge sort left half and merge sort right half after this point in the finished algorithm we should have two completely sorted halves and the last remaining step would be to merge those halves together so that's what we need to do here we need to write the code to merge these two sorted arrays into one large sorted array and to simplify our code a little bit we're actually going to write a method to do that just so we don't clutter up this merge sort method too much so we'll create a private static void method called merge now it needs to take in actually three things it needs to take in the inter array the original combined input array so it can merge the left and right arrays into it in sorted order and the left and right half arrays int array left half and int array right half similar to how we did in the merge sort method first we actually need the length of our left half and right half so we can do that the same way int we'll call it left size equals left half dot length and end right size equals right half dot length next is the part of the algorithm that can probably be the most confusing this is where we're going to be lubing through the elements in our left and right arrays of course from lowest to highest because they're already in sorted order comparing the first elements of each and adding the lower one to our merged array and keep comparing the lowest element of each array and adding the lower one to our merged array until we run out of elements in our left and right arrays so we actually need three iterator variables one for walking through the left half array one for walking through the right half array and one for walking through our merged array so to do that we'll need three ins that start at zero so we'll need int i equals zero and j equals zero and into k equals zero now if you want to be cool you can put all these in one line and just separate them by commas if they're all the same data types you can do this so you can just have int i equals zero j equals zero k equals zero and put all those in one line and look really cool i will be the iterator for our left half j will be the iterator for our right half and k will be the iterator for our merged array we'll actually use a while loop here and we're going to loop while i is less than left size and j is less than right size so this is basically looping until we run out of elements in the left array or we run out of elements on the right array so here what we actually want to do is compare the i th element of the left half with the jth element of the right half so we're saying here if left half at i is less than or equal to the right half at j then this is the smaller of the two numbers or they could be equal and it doesn't matter which one we add so we'll just add the one in the left half array we will add that element at left half i to our merged array we know that is the lowest element that we are looking at so far so we'll say input array at k which remember is our iterator for our merged array and set it equal to left half at i so now that this i element in our left half array has been added already to our input array our merged array we want to increment i to then look at the next element of the left half array so to do that we just say i plus plus now otherwise else so here we checked if our left half at i is less than or equal to the right half at j and if this wasn't the case and it didn't enter this if then we know that this j element of the right half is actually the smaller of these two numbers so in that case we would add the j element of our right half to our merged array and so that looks very similar to our code above we'll say input array at k set that equal to right half at j and then since we're adding the element that we found in the right half array we need to increment j so in the example here what just happened is we've just compared the first element of our left and right half arrays we've compared three with nine in this case three was less than nine so we add three to our merged array so here in our code it's as if this element in our left half array was less than the value we were looking at in our right half array this assignment is like adding 3 to our merged array and then we increment i which means we will shift from looking at this 3 to looking at this 27 and comparing it with the first element of the right array if the first element of our right array happened to be smaller then we would have added it to our combined array and increment it to look at the next element of the right array and that's what this else is accounting for now either way no matter if we added the element from the left or the right array either way we want to increment our combined array iterator which here is k so completely outside of that if else we want to do k plus plus now that we've set this first value we next want to set the second value so now this will keep looping through going through the arrays at each half and adding the lower element to our merged array until this condition is met which will go until we either run out of elements in our left array or run out of elements in our right array either way there's nothing left to compare but if we ran out of elements in either our left or right array we still have some numbers left in whichever array we didn't reach the end of and so after this while loop essentially we just need to do cleanup and add all of the elements that are still remaining in either the left or right array so using the smaller merge as an example first we start by comparing 27 and three three is lower so we add it and then we're comparing 27 to 43 27 is lower so we add it and then we move to comparing 38 with 43 38 is lower so we add it at that point we have added all the elements in this left array and there's nothing left so that would trigger this to exit the while loop but we still haven't added the rest of the elements from our right array and so we just need to loop through those remaining elements and add them to our merged list and in this point in the code it could be the left or the right arrays that have elements left over so we can just have code for both of them so to account for any possible elements left over in the left array we can say while i less than left size input array at k equals left half at i and then we went to increment the iterators of both i and k so how this works is if we already ran out of elements in our left array it would just bypass this completely and then we do the same for any remaining elements in our right array but just with different variables so we would say while j is less than right size then input array at k equals left half at j and we do j plus plus instead of i plus plus so at that point we've looped through each of our two halves constantly adding the lower of the two values to our merged array we loop through and add any remaining elements to the end of our combined array so now by the end of this merge method this input array will have all of the elements from the left and right half arrays combined in perfect order so now all that's left to do we've created our merge method we just haven't called it yet so here let's get rid of this and actually call our merge method with our left and right half arrays so what we have to give it is our original input array as we have here and then our left half and right half left half right half okay i think that completes the algorithm let's zoom out a little bit to have a look at our handy work but before we get too excited let's actually run it and make sure it works so here we'll do it with an array of just 10 elements let's give it a try ah i don't know we actually got an array index out of bounds exception so there's some problem somewhere where we're trying to reference an index of an array that doesn't exist we're trying to access like the fifth element of an array that only has four so let's click this line so we can see exactly where it's happening i see the problem it's a copy paste error i'm still using left half here when i should be using right half okay so that's an easy fix let's go ahead and run it again okay so we can see the before state here we started out with a completely unsorted list and then after it looks like this list is perfectly sorted okay so far so good that's looking great let's run it a few more times just to be sure looks good looks good looks good awesome okay so now that we have the algorithm working let's put it to the test right now we're only using 10 numbers let's crank it up let's do uh 10 000. run that so so it did that in in no time less than a second you couldn't even notice it so let's crank it up again and do a hundred thousand run that wow again pretty much instantaneous you know just one or two seconds it probably took more time to actually print out the sorted list than it did to actually do the sorting so 100 000 is that fast i don't see a reason not to keep going let's step it up to a million there goes printing out the randomly sorted list oh and it already is starting to print out the sorted lists and in that case in like seven seconds and really it looked like most of that time was just spent printing out the list themselves rather than actually doing the sorting so let's start getting nuts let's do 10 million okay it's printing out the unsorted list so it hasn't even started trying to sort them yet it has to go through all this printing before it even begins sorting let's see you'll see it stop for a second in a moment while it when it does its sorting okay it stopped now it's sorting and it's already done now it's printing out the list in sorted order so this is the part that's taking a while not the actual sorting so i think what we'll do next is now that we know that it's sorting the arrays properly we'll just comment out the actual printing of it so that we know that the amount of time that it takes is the amount of time that it actually took to sort the list and not just print it out that took about a minute to run but as you saw most of that time was spent just printing out the lists so let's go ahead and comment out both of our print array calls so we're still creating the random array and we're still sorting it but we're just not bothering to print it so we can get a good feel for exactly how long the actual sorting is taking and let's run it before okay and after so we know when it printed out the word after that meant it had already sorted the list so we can see up here that took about three seconds to sort an array of 10 million ins so of course that kicks the daylights out of the last two sorting algorithms we made of course it just wrecks bogo sort which took five hours for just 14 ins but also it's worlds better than bubble sort which took about 37 minutes to do a million this did 10 million in just a few seconds okay so it took four seconds to do 10 million let's let's keep going let's do 100 million how long is it going to take before sorting this one is taking a little bit longer but it's doing a hundred million after so it's done so it went from 11 35 19 to 11 35 43 so that is still less than 30 seconds that's less than 30 seconds to sort 100 million ins not to mention actually creating this random list and all of that but even setting that aside sorting a list that large in less than 30 seconds is awesome but hey i don't see a reason not to keep going let's see if we can do a billion what happens if we do a billion and run oh we ran out of memory it looks like we can't at least on my computer we can't create an array of a billion ins and sort them so at least on my computer java just doesn't have the amount of memory that it needs to do this sorting for a billion in so that's a little bit of a bummer i would like to have seen how long it would take but i mean that's okay that's a great problem to have we can sort so many numbers that the limitation is to the memory that we have on our machine rather than the speed of the algorithm so it looks like that's what an algorithm with big o of n log and complexity can do for you if you enjoyed this video or learned something please let me know by leaving a like and if you'd like to see more java videos like this one in the future be sure to subscribe so you don't miss the new video every week and really thank you for taking the time to like and subscribe it's the only way these videos get out to help more people and so i really do appreciate it and remember you can grab the source in the link below and so if you can run it on your computer and get it to work with a billion ins i would love to hear about it thanks for watching

Channel: Coding with John

Views: 8,138

Keywords: java merge sort, merge sort in java, merge sort in java using recursion, merge sort in java code, merge sort algorithm java, merge sort algorithm, java merge sort algorithm, analysis of mergesort, merge sort, recursive mergesort, java recursive mergesort, java mergesort recursive, codingwithjohn, coding with john, computer science, programming, java, java sorting algorithms, java sorting algorithms examples

Id: bOk35XmHPKs

Length: 23min 1sec (1381 seconds)

Published: Sun Apr 11 2021