Merge Sort Algorithm in Java - Full Tutorial with Source 

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 !

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.

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

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

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!!

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

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

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!!

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!

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

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!

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 RU-vid! Thank you for explaining this in a very easy way!

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).

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.

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

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!

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.

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

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.

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.

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

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

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

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

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

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

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.

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

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.

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

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

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.

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

seriously one of the best merge sort explanation

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.

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 :)

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

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.

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.

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

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

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

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

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

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

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

OMG, You are the best teacher I have ever seen

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!!

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

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

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

easiest explanation ever, keep up the good work.

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++; } }

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

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.

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

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)

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

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

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

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

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

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........💯🔥

Best one, getting addicted to your videos!!!

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

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

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.

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

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

the best...this algorithm stuck in my mind hardly

Thanks for explaining what other videos do not (@3:18)

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

You're an excellent teacher. Thank you.

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

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 :) .

nice explenation, i believe it helped me alot with my exams

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

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.

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

Thanks John! Very clear explanation

you just got yourself a like AND subscribe sir! this is the best one yet

Thank You very much. It was so clear that after video I wrote it myself with understanding what am I doing. Funny was, that I had the same mistake as in this video at 18.10 ))

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

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

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

I have always struggled with algorithms i never appreciated the big O notation until today 😎😎😎 i have seen the power of an algorithm

This tutorial made absolute sense. Could you explain binary search tree?

Thank you, this explanation is so clear and short.

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

simply the best in the java world, period!

ohhh thank you , finally I got what merge sort is 😊

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

Excellent explanation John

Thanks, your explanation is very clear.

You really made it look so easy and understandable

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

Super clean coding! Thank you

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.

Amazing teaching skills - perfection execution

That explanation was AMAZING ! Thank you !