Merge Sort Algorithm in Java - Full Tutorial with Source

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

You are Amazing broo, just keep going, I love it.

My go to video when I need to write a mergesort algorithm real quick. (Almost have it memorized at this point.) Maybe someone can illuminate me on one small problem I have had: When I have tried following this video to sort a List instead of an array I haven't had any luck. I have resorted to simply converting the list to an array, sorting it, and converting it back but if there is a more time-efficient way to tweak this algorithm for lists, I would appreciate feedback!

Should I account for the overflow that will happen when the sum of mid exceeds 2^31? this was a common bug in many implementations of binary search and merge sort.

in your mid variable you go mid = inputLength / 2 but for numbers 2^31 it'll cause an integer overflow interrupt.

Will this never happen? I know an integer array of that size is huge :D

Pure gold explainaition

Thank you so much for this!

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

its so so well explained and very easy to understand, thank you!!
BUT for me the explanation of the really crucial part is missing for me. For me it would be helpful to understand why we are calling the merge-method only one time and not recursively. i understand the algorithm like this: we split and split and split and split (recursively calling the mergeSort method) until exit condition is hit -> we only have arrays of one element... now we merge them togehter with calling the merge method... and here i dont understand, why this is enough. if we only merging the one-element-Arrays, we would just have a two element array right? how are we getting to the sorted array with the initial array length? maybe someone can help me finding where i am thinking the wrong way, i must be wrong, bc the algorithm apparently works.... thanks for help

Thanks for the video , I just don’t get it why do we need to check additional time if the element left, on either left or right half if the condition is I less than the left size AND j is smaller than the right size.

Hi John, Your videos are really very detailed and easy to understand. Thanks for all your effort to help others. I do have a clarification I would like to ask, in your explanation about merge sort technique you mentioned once you split the array you already have sorted partitions. But is it not the case that when you split the array into two halves, it just splits not sorts, and when actually "merge" you compare, sort and add elements to the final array?. Please correct me if I am wrong. Thanks!!.

Years later I did this on my M1 Max. 1 billion floats also caused my machine to get a java heap error.

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

Thanks for the awful video

ChatGPT informed me that you can sort the arrays in-place in order to use less memory. It took 2 minutes and 8 seconds to sort 1 billion ints. Memory usage was insane! According to task manager, it was using around 8GB.

you are seriously awesome

THank you for the explanation. But my below code not working. May I know what mistake I am doing here?
package sorting;

import java.util.Arrays;

public class S04_MergeSort {
private static void mergeSort(int[] arr) {
int inputLength = arr.length;

if (inputLength < 2) {
return;
}

int midIndex = inputLength / 2;
int[] leftHalf = new int[midIndex];
int[] rightHalf = new int[inputLength - midIndex];
for (int i = 0; i < midIndex; i++) {
leftHalf[i] = arr[i];
}
for (int i = midIndex; i < inputLength; i++) {
rightHalf[i - midIndex] = arr[i];
}

mergeSort(leftHalf);
mergeSort(rightHalf);

// merge them
merge(arr, leftHalf, rightHalf);

}

private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf){
int leftSize = leftHalf.length;
int rightSize = rightHalf.length;

int i=0, j=0, k=0;

if(i<leftSize && j <rightSize) {
if(leftHalf[i] <= rightHalf[j]) {
inputArray[k] = leftHalf[i];
i++;
} else {
inputArray[k] = rightHalf[j];
j++;
}
k++;
}

while(i< leftSize) {
inputArray[k] = leftHalf[i];
i++;
k++;
}

while(j< rightSize) {
inputArray[k] = rightHalf[j];
j++;
k++;
}
}



public static void main(String[] args) {
int[] nums = {8, 71, 12, 0, 18,53, 17, 49, 8};
mergeSort(nums);
System.out.println(Arrays.toString(nums));
}
}

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

straight to my brain .thanks!

Awesome exaplained and easy to understand 😇😊

Amazing video! Just one question. Is the merge function only used to put the last 2 sets of numbers in place or does it put all the numbers in their correct order? Thanks

Thank you for this great tutorial!

Make a DAS course, people will buy it like there is no tomorrow...believe me you got super skills ..... lot better than Udemy instructors.

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)

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.

Very nice. But the proper solution would be not creating new arrays for each merge, but to pass the positions instead. A memory copy is pretty fast, but not when you do trillions of them.
public static int [] mergeSort(int [] numbers, int start, int end) {....}

Awsome algorithm!

Omg...You sir deserve a cape 🫡

This is the best explanation of merge sort I've ever heard. Thank you!!

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

这是归并排序吗

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.

It feels like getting coding lessons by Jonny Sins, he looks like you. 😂😂
BTW thanks a lot for making our learning journey easier. I get the topics to study from other websites and then watch your videos to truly understand the concept. ❤

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.

Thank you

You're an excellent teacher. Thank you.

Great video, thanks

I didnt understand why after first algorithm we should have two sorted pieces doesnt first algorithm just cuts them into two pieces eat everytime how can we be sure that in the last step we got 2 sorted arrays

Can you make a video about Heap sort .I really need it for my test .Pls John

This is super helpful and very well presented! Thanks!

worked amazing!

best explanation ever

The video is made in a simple manner that anybody can understand. Thanks for that. The memory is allocated for keeping the splitted array, I can think the memory will be deallocated when it goes out of context. Is it good practice to do the free also? If so where it need to be added. Thanks.

my question is how did the leftHalf and rightHalf sort itself? i understand that we broke it up into halves until there was 1 or less elements in the array but how did it sort into increasing order?

thanks

package practice;

import java.util.Random;

public class mergeSortMain {

public static void main(String[] args) {

Random random = new Random();
int n = 10;
int arr[] = new int[n];

for (int i = 0; i<n; i++)
{
arr[i] = random.nextInt(10);
}

displayArr(arr);

mergeSort(arr);

displayArr(arr);

}

private static void mergeSort(int[] arr) {

int len = arr.length;

if(len < 2) {
return;
}

int mid = len/2;
int[] leftArr = new int[mid];
int[] rightArr = new int[len - mid];

for(int i =0;i<mid;i++) {
leftArr[i] = arr[i];
}
for(int j = mid;j<len;j++) {
rightArr[j-mid] = arr[j];
}

mergeSort(leftArr);
mergeSort(rightArr);

merge(arr,leftArr,rightArr);
}

private static void merge(int[] arr,int[] leftArr , int[] rightArr) {

int leftLen = leftArr.length;
int rightLen = rightArr.length;

int i=0 , j=0 , k=0 ;

while(i < leftLen && j < rightLen) {
if(leftArr[i] <= rightArr[j])
{
arr[k] = leftArr[i];
i++;
}
else
{
arr[k] = rightArr[j];
j++;
}

k++;
}

while(i<leftLen) {
arr[k] = leftArr[i];
k++;
i++;
}
while(j<rightLen) {
arr[k] = rightArr[j];
k++;
j++;
}

}

public static void displayArr(int arr[]) {
int len = arr.length;
for(int i = 0 ; i<len ; i++) {
System.out.print(" "+arr[i]);
}
System.out.println();
}

}

Can anyone explain how the recursive methods keep dividing until there's only one element left in an array? That too without having a specific condition provided?

I am confused about merge. After we mergesort the data, left and right will be only one number right? And then we merge these two number and so on. It is also like a recursion and how can it work?

OMG, You are the best teacher I have ever seen

Loved every second of it!

haha that was maniacal i love it