Merge Sort Algorithm in Java - Full Tutorial with Source

[@nguyencongthaisonk14hcm57]

I'm very weak in algorithms. From watching your video, the tutorial is very easy to understand. I understand how merge sort works. Thank you very much from the Vietnamese guy !

[@CodingWithJohn]

Thanks Vietnamese Guy! Very glad I was able to help!

[@akosdanielbollok]

This is pure gold! I wish you did a full Data structures&algorithms course, that would be awesome.

[@metdelta1]

Perhaps the BEST explanation of Merge Sort out there. 👍🏻 The code along with variable names, justifies the natural thinking of the human mind. Thanks a lot ❤️ Subscribed ✅ Best wishes and hope your channel gets all the love and support it deserves.

[@marvinzelaya1145]

Agreed, he explained it clearly and step by step, such a great explanation!!!

[@sadekjn]

Professors at top CS programs like UC Berkeley (where I suffered) aren't able to explain this stuff as well and as clearly as you in multiple 2-hour-long lectures. From the bottom of my heart, I thank you for existing.

[@moeal5110]

I watched and read neumors explanations about this but only after watching your video I was able to understand each line and now I can see it in my brain's eyes. I also dreamt about it. Thanks a lot! Please do more

[@taldennis8058]

This video is something else, I watched all the big channels before I got here, this explanation is by far the most detailed and the most accurate, also providing an explanation for all the edge cases. the implementation is super clear and clean. this channel is underrated, I wish I knew this channel earlier. thank you so much, you're the best!!

[@TuanBuianonymous]

agree

[@pranusharavula2943]

Agreed yeah

[@timjoyalle318]

I had to watch more than once to really absorb the info. It still is a lot less time and money than it costs me to listen to lectures at my university. Thank you for taking the time to make this video!

[@AceNinja1101]

Very informative video! Really could have used this back when I was in college lol. Also just attempted to run this with 1 billion elements and took about 8 and half minutes using C# for anyone who's curious!

[@davudazizov4966]

I have to tell this, I've been trying to understand merge sort for quite a few days, and this video is the best I've found on KZbin! Thank you for explaining this in a very easy way!

[@cr8444]

I can't thank you enough for this clean explanation. I haven't been able to understand this algorithm until I stumbled on your video. Now I practically know what each line of code means. You're a genius!!

[@elshaterhassansaber7644]

I've been searching for a good explanation and a good clean code but luckily !! i found both in one video you're an amazing guy

[@jaydeeppawar1720]

true a clean code is a must for understanding ....

[@LizyAd]

Out of every video I have watched on Merge Sort, you broke it down the best. I really appreciate you John. Thank you so much.

[@Mr.Grave.]

Career jumping here. Really appreciate your work to provide these great tutorials for free.

[@akshaypatel9982]

Wow, the first explanation that made complete sense with 0 confusion.Thank you very much! Wish you were my teacher back in college lol

[@TuanBuianonymous]

my english is not good to understand all words you said but when i look into your code i absolutely understand all, thank you very much.

[@timurboltaev8688]

Thank you. Watched the video. Went to the code. Copied it down with a pen on paper to understand better. Rewatched the video. I think I have grasped it.

[@Yersinia1988]

I was so frustrated and sad about not understanding the merge sort. Your explnation is very clear, made my day. Thanks a lot! :)

[@neurohan]

You are, without a doubt, one of the most talented educators I've come across (both online and offline).

[@hive_san615]

I just started DSA recently and was stuck at merge sort for two days, understood the concept but not why code was written the way it was. You cleared all the doubts thanks you very much.

[@raoulkid]

The only person on yt that actually explained the merge subroutine properly, thanks, +1 sub

[@AliBulut-tg6bh]

We all have been taught that merge sort is a fast efficient but memory poor algorithm. But to actually see that happen really changes things. I think it was the first time I saw someone pushing the algorithm to its limit memory-wise. Thank you sir, it was a great explanation.

[@kosaken1207]

Absolutely brilliant explanation! I was so confused for a school assignment on why the last two while loops exist in the code. Turns out it was just cleanup!

[@sujanreddy9770]

Whenever I need to refer algorithms I will directly watch your videos thanks for explaining so clearly.

[@HisExcellencyAKK]

Great work! possibly memory can be improved a bit by passing indices (start, mid, end) into split subroutine instead of sub arrays. We would only need an auxiliary space of size n at merge subroutine. Since merge subroutine happens after split subroutines, the maximum auxiliary space that will be needed is n instead of n*log(n).

[@natnal9587]

Honestly, this is the best video I have ever seen about merge sort.

[@sekharsamanta6266]

Hi Mr. John, I've seen so many videos on different algorithms of other people but your explanation is crystal clear and unique

[@franklinoduro7274]

Hands down this is the best sorting algorithm video i have seen on youtube. Thanks John

[@J-wm4ss]

Thanks! This makes SO MUCH MORE SENSE than other explanations!

[@sajanarora245]

Gave the link to this in the comments of every video I watched to understand merge sort because this is the best explanation of Merge sort. Thanks a lot man!!! Subscribed

[@wasekasi]

This is by far the best sorting app I've seen someone code. Awesome.

[@RanVargas]

Hey Man, I just wanted to comment and say I really thank you, I hadn't fully understood Merge Sort at least on the Merge step, but now I am kind of like grasping it, thank you for explaining with time and detail.

[@haidaralihammoud2686]

That is by far the best explanation out there! Amazing technique of teaching and breaking it down. Thanks a lot!

[@Nerdymelreads]

You do not know how much I looked around for a better explanation. You nailed it. Earned a new subbie.

[@HelicopterRidesForCommunists]

You are such a good teacher. Very talented at communicating information and concepts. 1 million sorted thanks to you.

[@annkit87]

Thanks for the great explanation @Coding with John. I tried to make the program more detailed with step by step recursive calls and some visualization in source code & output. Implementation with example explanation & tried to visualize every recursive call until it returns back the control to the calling function. PS: Please do not confuse with code written for printing left & right parts at specific levels in the recursive calls, that is only for visualization the flow for better understanding. private static void mergeSort() { int[] elements = {22, 14, -7, 56, 3}; System.out.println("Input Array: " + Arrays.toString(elements)); // Split array into 2 parts until we get single sorted element // Merge every subset of elements using temp sorted array performMergeSort(elements, 0, elements.length - 1, 1); System.out.println("Sorted Array: " + Arrays.toString(elements)); } private static void performMergeSort(int[] elements, int start, int end, int levels) { // Follow the steps below the solve the problem: // MergeSort(arr[], l, r) // If l < r // Find the middle point to divide the array into two halves: // middle m = l + (r - l)/2 // Call mergeSort for first half: // Call mergeSort(arr, l, m) // Call mergeSort for second half: // Call mergeSort(arr, m + 1, r) // Merge the two halves sorted in steps 2 and 3: // Call merge(arr, l, m, r) if (start < end) { int mid = start + (end - start) / 2; // split elements into 2 parts - left & right // recursively do this until we get reach at single element for(int l =0; l < levels; l++){ System.out.print("\t"); } System.out.println("START: " + start + ", MID: " + mid + ", END: " + end + ", LEVEL: " + levels); performMergeSort(elements, start, mid, levels+1); performMergeSort(elements, mid + 1, end, levels+1); // merge back left + right elements after comparing their values merge(elements, start, end, mid, levels); } // 22, 14, -7, 56, 3 // legends: start => s, end => e // (s < e) == (0 < 4) == true // 0 + (4 - 0)/2 = 2 = mid // left = performMergeSort(elements, 0, 2); 22, 14, -7 // (s < e) == (0 < 2) == true // 0 + (2-0)/2 = 1 = mid // left = performMergeSort(elements, 0, 1); 22, 14 // (s < e) == (0 < 1) == true // 0 + (1 - 0)/2 = 0 = mid // left = performMergeSort(elements, 0, 0); 22 // (s < e) == (0 < 0) == false => return; // right = performMergeSort(elements, 1, 1); 14 // (s < e) == (1 < 1) == false => return; // merge = left + right (while sorting) = merge (elements, 0, 1, 0) // right = performMergeSort(elements, 2, 2); -7 // (s < e) == (2 < 2) == false => return; // merge = left + right (while sorting) = merge (elements, 0, 2, 1) // right = performMergeSort(elements, 3, 4); 56, 3 // (s < e) == (3 < 4) == true // 3 + (4-3)/2 = 3 = mid // left = performMergeSort(elements, 3, 3); 56 // (s < e) == (3 < 3) == false => return; // right = performMergeSort(elements, 4, 4); 3 // (s < e) == (4 < 4) == false => return; // merge = left + right (while sorting) = merge (elements, 3, 4, 3) // merge = left + right (while sorting) = merge (elements, 0, 4, 2) } private static void merge(int[] elements, int start, int end, int mid, int levels){ // declare 2 temp arrays in every merge call // (elements, 0, 1, 0) // mid - start size + 1 (0 - 0 + 1) = 1 // end - mid size (1 - 0) = 1 // left[] = 0 -> 22 // right[] = 1 -> 14 // (elements, 0, 2, 1) // mid - start size + 1 (1 - 0 + 1) = 2 // end - mid size (2 - 1) = 1 // left[] = 0 -> 14, 1 -> 22 // right[] = 2 -> -7 // (elements, 3, 4, 3) // mid - start size + 1 (3 - 3 + 1) = 1 // end - mid size (4 - 3) = 1 // left[] = 0 -> 56 // right[] = 1 -> 3 // (elements, 0, 4, 2) // mid - start size + 1 (2 - 0 + 1) = 3 // end - mid size (4 - 2) = 2 // left[] = 0 -> -7, 1 -> 14, 2 -> 22 // right[] = 0 -> 3, 1 -> 56 int[] left = new int[mid - start + 1]; int[] right = new int[end - mid]; for(int l =0; l < levels+3 ; l++){ System.out.print("\t"); } System.out.print("LEVEL: " + levels+" "); for(int leftCounter = 0; leftCounter < left.length; leftCounter++){ left[leftCounter] = elements[start + leftCounter]; for(int l =0; l < levels+3 ; l++){ System.out.print("\t"); } System.out.println("LEFT PART: " + elements[start + leftCounter]); } for(int l =0; l < levels + 3; l++){ System.out.print("\t"); } System.out.println("Left Array: " + Arrays.toString(left)); for(int rightCounter = 0; rightCounter < right.length; rightCounter++){ right[rightCounter] = elements[mid + rightCounter + 1]; for(int l =0; l < levels + 3; l++){ System.out.print("\t"); } System.out.println("RIGHT PART: " + elements[mid + rightCounter + 1]); } for(int l =0; l < levels + 3; l++){ System.out.print("\t"); } System.out.println("Right Array: " + Arrays.toString(right)); // int[] merged = new int[left.length + right.length]; int i = 0, j = 0 ,k = start; // declared merged array of size = left + right = 2 while ( i < left.length && j < right.length) { if (left[i] < right[j]) { elements[k] = left[i]; i++; k++; } else { elements[k] = right[j]; j++; k++; } } // copy remaining already sported elements in merged array from left array while ( i < left.length) { elements[k] = left[i]; i++; k++; } // copy remaining already sorted elements in merged array from right array while (j < right.length){ elements[k] = right[j]; j++; k++; } }

[@mahmoudmoussa6722]

For such comprehensive&best merge sort out there, you won a subscriber. Thanks.

[@sagarrawal7740]

seriously one of the best merge sort explanation

[@abhishekhm1264]

I cannot believe this channel exists. The way he explains!!!. Just Awesome!!.

[@igor9919]

This is by far the best tutorial for merge sort, thanks so much

[@LTZMSYAL]

John you did an awesome job in this video! You're the best course I could find on the merge sort algorithm. I really want to thank you from France for that. Keep up the good work :)

[@nosehad5486]

great, you are the only one that explained it in a way that i understand

[@mukeshprakash8112]

Wouldn't be able to get a more clear explanation for Merge Sort and at the same time can't believe Johnny Sins became a programmer as well lol(no offense. keep up the good work man

[@ryandailey1496]

You said the equals in the "if (leftHalf[i]

[@tanvirkazirocks]

f (leftHalf[i]

[@doncilaarcadie]

Finally I got this!!! Thank you!!! The best explanation so far!!!

[@chrismendez1177]

Seriously I love the content you make, its made my learning much more better. You're so relaxed and calm about the way you explain your code. Good job!!

[@eduardohenriquedeassis9729]

Hey Bro, it is for sure, one of the best tutorial about this subject I ever saw, I was struggling to understand it, but now it´s clearwater!!!!! Thanks for that. Greetings from Brazil.

[@aparajithasaravanakumar7998]

OMG, You are the best teacher I have ever seen

[@sheriffcrandy]

Thanks bro this helped me a lot

[@kushalmondal618]

With this Explanation any one can write Merge sort on their first Program , Subscribed quickly , Never gonna miss the chance to get better explanations of Hard topics, Like your work........💯🔥

[@HelicopterRidesForCommunists]

My computer can likely handle the billion ints. This was so great. Please continue making tutorials!

[@__nitinkumar__]

Hey John, You are probably the test instructor I have ever seen. I used to get scared of Merge Sort just by looking at it's algorithm. Now seeing the implementation, it's actually pretty easy. Thanks for making it look so simple and writing as well.

[@kamdave1895]

only moved up to 100 million before I ran out of memory. However thanks for taking us through this algorithm step by step. It made the quick sort algorithm easier to understand.

[@onestopautomationmerasaab5098]

Please please do make videos on all algorithms. Its the best and non confusing explanation ever. Cheers mate.

[@mir.9805]

I can't believe I've watched this entire video and without being bored. I can't even sit in class for 15 minutes without going to sleep and I'm literally watching this at 2:32am in bed.

[@mesbahied4284]

2:11 HHHHHHHHH

[@jacobkreifels7690]

These sorts always made no sense but you made it super simple

[@hawagiri4035]

easiest explanation ever, keep up the good work.

[@rishijuvekar7572]

What an excellent explanation !! Simple, clear and concise. Thank you very much.

[@celinareger2704]

I really like your explanation. I watch many other videos befor and as a biginner I understand nothing but your examples are really good and understandable. 😊 Also you're make it really interesting.

[@kevalkrishna4134]

Such a calm and beautiful explanation for merge sort algo , loved it. And yeah ,you earned a new subscriber.

[@juanrada1940]

Fantastic video! "If you want to be cool you can..." is priceless!

[@sagarkalburgi]

This was so easy to understand, no wonder you have so many views on your videos. Thanks!

[@hehhehdummy]

Best lecture on the subject I've come across. Love the demo at the end too. I know there's a way to write this algorithm with 1 helper array (instead of creating new arrays all the time), it seems not to have mattered too much.

[@sriplano748]

Thanks John for a real good explanation of Merge Sort algorithm with code.

[@lyn8964]

Your videos let me fall in love with java! So much Java fun!

[@MrRobschke]

This video is insanely well made!! Good job :)

[@pelinegriboyun948]

awesome video! couldn't understand merge sort at all before this explanation, thank you so much

[@pontierent734]

I know its not really that important, but for copying the left and right, I think it would make it more understandable to loop from the length of the respective arrays, and for the right half just add the midpoint index to the original arrays index.

[@CodingWithJohn]

Thanks, I like the idea! I'm always looking for ways to make my code as clean as possible. When preparing this video I saw some implementations that took the length of each array as additional parameters instead of just looking at the array, which I thought was ridiculous. I also saw some that incremented indexes on the same line as doing assignments (leftHalf[i++] = inputArray[k++], etc), which works fine of course but I think can be unnecessarily confusing, especially for learners.

[@pontierent734]

@@CodingWithJohn I also saw that, but it definitely would be confusing to learners so it was probably better to put them on separate lines.

[@paulsnehasish5830]

im new to this channel and already loving the short gem contents

[@moorefunandgames7411]

Me too I just started an apprenticeship recently for Software Engineering and this channel has helped a ton on understanding some of the more complex features of the Java language.

[@davidl6797]

Great explanation John! It was easy to learn and understand this algorithm with your lesson!

[@tulioperez6011]

Amazing teaching skills - perfection execution

[@madhavansan008]

You are born to teach ! , Expecting more and more videos

[@kishordige9721]

Best one, getting addicted to your videos!!!

[@LONELY-x9k]

I know I am quite late to the party, but I really really liked your explanation and your code. A downside of using mergesort is because of the ammount of memory it requires. As you can see from your explanation, sorting an array of 1b ints means creating 1b arrays which can use a LOT of memory, now think of sorting 1b float, or other data-types which are much bigger. Mergesort is one of the quickest, easiest sorting algorithms but the obvious downside is because of how many resources it uses.

[@fakhrulmb]

Subscribed! Helped me through my Algo and data structure unit!! Best coding tutorial out here!!

[@rodrigosalomao3835]

I've finilly learned this. Thanks a lot dude!

[@AamirBilalm]

Great work John, really appreciate it. Highly undervalued channel. Hope you get the support you deserve.

[@kunaldutta7096]

Very good illustration and easy to understand steps. I have stumbled upon the videos of John by accident, and I am really happy that I have. Kudos to you. subscribed :) .

[@wilsvenleong96]

Definitely the best explanation out there. I'm subscribed.

[@ferhatf9385]

thanks alot i was reall struggling to learn merging sorted arrays ,but this video rwas eally helped me then all the others that i watched

[@_Anna_Nass_]

Thank you so much! This was super helpful for my assignment. I feel like I really understand now.

[@trentlandon9033]

You really made it look so easy and understandable

[@martinemanuel8239]

It's just the best explanation I ever seen, thank you so much !

[@asmaasadek7735]

Just wanted to tell you, you are one of the best!

[@georgikyshenko4380]

That explanation was AMAZING ! Thank you !

[@crazyedits6948]

I am looking for this kind of explanation for a long time. Thank you so much john for this extraordinary tutorial. Loved it and subscribed immediatley.

[@Svinqvai]

Great explanation. I would like a section at the end where you clean the code. Because you are lead dev you know you cannot have such code with 6 while loops and 3 for loops to sort an array. This code needs refactoring. That part would be beneficial. For example: using System.arraycopy or Arrays.copyOfRange to populate the left and right half of the array.

[@okgus1]

Could he also have just passed the original array each time, just setting the starting/ending indexes of each sub array, so as to sort the "sub-arrays" in place, without having to allocate so much extra memory for each sub array?

[@cesar-on-youtube]

You're an excellent teacher. Thank you.

[@michaellese3604]

Great video, super easy to follow and made understanding merge sort way easier

[@mariusandries4103]

Thank you, this explanation is so clear and short.

[@ayyanchira]

Really good explanation! Thanks John! Your videos are spot on!

[@MelonHusk7]

Thank u john for putting it in my head! u got a lifetime subscriber.

[@MrThemarsu]

soooo much better explanations than my lessons..... thx!

[@juanjaureguireyes]

Hi John! Thanks a lot for your video. Quite helpful for my C++ programming assignment. Cheers!

[@ВиталийКомлев-р8б]

Awesome explanation! As usual!!! Thank you, John, so much!!!! You're the best!!😊

[@InvinciRD]

I would be heavilyy grateful if make more vdos of such kind...y=you have the potential of conquering the market(by market i mean the hearts of students as your speech of explanation is crystal clear)

[@thetruthsayer8347]

I like this. I wish there more algorithm tutorials based in java. Please make more.

[@ValenciaTheMan]

I guess even on a paid udemy course u still get a complicated explanation of mergesort with a difficult java code. This is clear and readable code, tahbk you very much, i could understand zhis clearly.

[@willemvanderveen7567]

Keep it up man, your videos are absolutely amazing

[@nickynicole4030]

Thanks John! Very clear explanation

[@fdrjanosch]

Thank you very much for uploading this video. Greetings from Germany!